Грамматика BNF для набора правил

у меня проблема

(a) Дайте грамматику, используя правила BNF, для построения программы на языке "безмозглый". Безмозглая программа должна следовать правилам: программа должна начинаться и заканчиваться словом «endstart». В языке есть три типа операторов: печать, чтение и вычисление. Эти операторы могут появляться в любом порядке, за исключением того, что печать может происходить только сразу после оператора compute. Это любая непустая строка из прописных букв. Ваш BNF также должен определять. Пример юридической программы witless: endstart читать SAM читать TED вычислить вычислить печать FRED вычислить чтение TIM endstart (b) Ваша грамматика неоднозначна? Поясните свой ответ.

Я пришел к следующему решению. Но мне нужно убедиться, что это правильно.

<witless_program>::=endstart <statement> endstart
<statement>::=<read>|<compute>
<read>::='read' <var>|<statement>
<print>::='print' <var>
<compute>::='compute' | 'compute' <print>|<statement>
<var>::=<letter> | <var><letter>
<letter>::=A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z

Грамматика кажется однозначной. Я прав?


bnf context-free-grammar formal-languages automata
person ProgrammingPanda    schedule 21.08.2014    source источник
comment
Похоже, что вопрос был искажен по ходу дела; предложения Здесь любая непустая строка заглавных букв, и Ваш BNF должен определить, также кажутся неполными.   -  person C. M. Sperberg-McQueen    schedule 28.08.2014

Ответы (1)


arrow_upward
1
arrow_downward

Похоже, ваша грамматика немного нарушена. Предположим, что кто-то выбирает вывод, подобный следующему:

program --> endstart <statement> endstart
--> endstart <read> endstart
--> endstart read <var>

Используя текущую грамматику, вы не сможете использовать рекурсию для продолжения предложения на языке, поскольку после того, как нетерминальный var был полностью выведен, не будет никаких обратных ссылок на нетерминальный оператор < / em>.

Я бы рассмотрел следующую грамматику в соответствии с вашими потребностями:

<statement> --> <read> | <compute>
<read>      --> read <var> <statement> | read <var>
<compute>   --> compute <print> <statement> | compute <print> | compute <statement> | compute
<print>     --> print <var>
<var>       --> <letter> | <letter><var>
<letter>    --> A|B|C|...

Теперь давайте вывести предложение «endstart read SAM read TED compute compute print FRED compute read TIM endstart», используя подстановку LHS:

program --> endstart <statement> endstart
--> endstart <read> endstart endstart
--> endstart read <var> <statement> endstart
--> endstart read <letter><var> <statement> endstart
--> endstart read S<var> <statement> endstart
--> endstart read S<letter><var> <statement> endstart
--> endstart read SA<var> <statement> endstart
--> endstart read SA<letter> <statement> endstart
--> endstart read SAM <statement> endstart
--> endstart read SAM <read> endstart
--> endstart read SAM read <var> <statement> endstart
--> endstart read SAM read <letter><var> <statement> endstart
--> endstart read SAM read T<var> <statement> endstart
--> endstart read SAM read T<letter><var> <statement> endstart
--> endstart read SAM read TE<var> <statement> endstart
--> endstart read SAM read TE<letter> <statement> endstart
--> endstart read SAM read TED <statement> endstart
--> endstart read SAM read TED <compute> endstart
--> endstart read SAM read TED compute <statement> endstart
--> endstart read SAM read TED compute <compute> endstart
--> endstart read SAM read TED compute compute <print> <statement> endstart
--> endstart read SAM read TED compute compute print <var> <statement> endstart
... play the same game to spell out FRED ...
--> endstart read SAM read TED compute compute print FRED <statement> endstart
--> endstart read SAM read TED compute compute print FRED compute <statement> endstart
--> endstart read SAM read TED compute compute print FRED compute <read> endstart
--> endstart read SAM read TED compute compute print FRED compute read <var> endstart
... play the same game to spell out TIM ...
--> endstart read SAM read TED compute compute print FRED compute read TIM endstart

Теперь, когда у нас есть вывод, можно решить проблему двусмысленности. Вам следует задать вопрос, есть ли в грамматике дополнительное дерево синтаксического анализа. Уловка заключается в том, чтобы смотреть на грамматику и пытаться идентифицировать любые нетерминалы, у которых есть продукты, которые содержат экземпляр самого себя, который может привести к тому или иному пути. Считать

<statement> --> <statement><statement> | some_terminal

Для такого рода продукции синтаксический анализатор должен решить, по какому пути идти вниз (в данном случае, какой оператор заменить первым). Если в вашей грамматике нет произведений с таким свойством, обычно это однозначно.

И отвечу на ваш вопрос - нет, исправленная грамматика не неоднозначна.

person 8bitoverflow    schedule 14.01.2015