BNF для шестнадцатеричного числа

В качестве домашнего задания я должен написать определение БНФ для шестнадцатеричного числа <hex>.

Это должно быть сделано с помощью <digit> и <letter>, оба из которых определены следующим образом:

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= A | B | C | D | E | F

Ответ учебника дается как:

<hex> ::= <digit> | <letter> | <hex> <digit> | <hex> <letter>

Я согласен, что это правильный ответ, но я хотел бы спросить, правильно ли также давать следующий ответ:

<hex> ::= <digit> | <letter> | <hex> <hex>

grammar bnf context-free-grammar
person user12205    schedule 28.01.2015    source источник
comment
он производит тот же язык, но он неоднозначен.   -  person 1010    schedule 28.01.2015
comment
<hex> <hex> никогда не узнает, следует ли уменьшать до <letter> <hex> или <hex> <digit> в случае чего-то вроде A20C64. Это и делает его двусмысленным.   -  person    schedule 28.01.2015
comment
Примечание для себя: Связано: math.stackexchange.com/q/22463/208787   -  person user12205    schedule 28.01.2015

Ответы (1)


arrow_upward
1
arrow_downward

Нет, просто посмотрите на деревья синтаксического анализа, созданные грамматикой учебника по сравнению с рекомендуемая грамматика (код). Примечание: деревья синтаксического анализа представляют производные.

person rns    schedule 28.01.2015
comment
некоторые генераторы синтаксических анализаторов могут разрешать неоднозначности, определяющие отношения приоритета или ассоциативности. верна ли вторая грамматика или нет, зависит от контекста, в котором она будет использоваться. - person 1010; 28.01.2015
comment
@ 1010 - конечно, но в этом случае дерево синтаксического анализа, созданное грамматикой учебника, не входит в число деревьев синтаксического анализа, созданных второй грамматикой. Кроме того, языковое равенство. Имея две CFG, генерируют ли они один и тот же язык? неразрешима -- goo.gl/rJeEfS. - person rns; 28.01.2015
comment
разные грамматики будут иметь разные деревья синтаксического анализа. - person 1010; 29.01.2015
comment
неразрешимость эквивалентности двух КФГ означает общий случай любых двух грамматик. будут частные случаи, когда можно продемонстрировать, что две грамматики порождают один и тот же язык. - person 1010; 29.01.2015
comment
Будет, да, но я не вижу способа сделать это в данном случае, ср. Комментарий Хроно Кицунэ выше. Хотя я хотел бы оказаться неправым. - person rns; 29.01.2015
comment
индукцией по длине строки можно доказать, что любая строка шестнадцатеричных цифр может быть получена с помощью этих грамматик. с другой стороны, любая строка, полученная из этих грамматик, будет строкой шестнадцатеричных цифр, поэтому их язык представляет собой набор шестнадцатеричных чисел. - person 1010; 29.01.2015