Регулярное выражение для грамматики

Question

Я читаю конечные автоматы & грамматик из компоновки компилятора Ахо, и я так долго придерживаюсь этой грамматики. У меня нет четкого представления о том, как я могу это описать:

Рассмотрим следующую грамматику:

S -> (L) | a L -> L, S | S

Обратите внимание, что круглые скобки и запятые являются терминалами на этом языке и отображаются в предложениях, принятых этой грамматикой. Попробуйте описать язык, сгенерированный этой грамматикой. Является ли эта грамматика неоднозначной?

Мое беспокойство здесь: Может ли язык, сгенерированный этой грамматикой, описываться как регулярные выражения? Я смущен тем, как это сделать. Любая помощь?

Answer 1

Чтобы показать, что грамматика неоднозначна, вы должны иметь возможность построить два разных дерева синтаксического анализа при разборе одной и той же строки. Ваша строка будет состоять из «(», «)», «,» и «a», так как это единственные символы терминала в грамматике.

Попробуйте выполнить эти четыре символа терминала несколькими способами и посмотреть, сможете ли вы показывать разные успешные парсы в духе example ambiguous grammar on Wikipedia.

Немедленная левая рекурсия имеет тенденцию вызывать проблемы для некоторых парсеров. Смотрите, если «а, а, а» делает что-нибудь интересное на «L → L, S | S» ...

мое беспокойство здесь язык, порождаемый этой грамматикой, как регулярное выражение, оно может быть описано ... Я не понимаю, как это сделать

Регулярное выражение не может полностью описать грамматику. Перезапись часть грамматики сделает это более очевидными:

1. S → (L)
2. S →
3. L → L, S
4. L → S

Обратите внимание на # 1 и # 4. L может производить S, а S может производить (L). Это означает, что S может производить (S), который может производить ((S)), (((S))) и т. Д. До бесконечности. Главное, чтобы скобки совпадали; есть такое же количество символов («символы как»).

Регулярное выражение не может этого сделать.

Регулярные выражения относятся к конечным автоматам. Конечные автоматы не могут рассчитывать. A Язык L ∈ {w: 0 ^{n n}} не является регулярным. L ∈ {w: (ⁿ) ⁿ}, просто быть заменой "(" для "0" и ")" для "1" также не является. См. Первый раздел примеров под номером Regular Languages - Wikipedia. (Нотация примечание: s является S, S является сс, ..., с ^п в ы повторяется п раз.)

Это означает, что вы не можете использовать регулярные выражения, чтобы описать ту часть языка. Это ставит его в область CFG, Turing Machines и pushdown automata.

Answer 2

Регулярные выражения (и библиотека для их интерпретации) являются плохим инструментом для распознавания предложений контекстно-свободной грамматики. Вместо этого вы хотели бы использовать генератор синтаксического анализатора, такой как yacc, bison или ANTLR.

Я думаю, что смысл упражнения в книге Ахо заключается в том, чтобы «описать язык» словами, чтобы понять, является ли он двусмысленным. Один из способов приблизиться к нему: можете ли вы разработать грамматическое предложение, которое может быть проанализировано двумя разными способами, учитывая постановки грамматики? Если это так, то грамматика неоднозначна.