вопрос по синтаксическому анализу Опции

[1147]

нужно произвести синтаксический анализ - "вариант". Я сначала думал что нужно создать программу, анализирующую само выражение "вариант", но вскоре понял что это не так. Кроме того непонятно как должен выглядеть алфавит языка записи выражения, соответственно я немогу построить таблицу переходов..
Буду благодарен за любую помошь в этом вопросе

Сообщение отредактировано: 1147 - 26.11.2008 20:26

[Archon]

Извини, что так долго, только сейчас в интернет вышел.

Разработать программу, которая выполняет лексический и синтаксический анализ в соответствии с заданной синтаксической диаграммой. Программа должна обеспечивать многократный ввод предложений, их об-работку с выводом на экран результатов лексического и синтаксического анализов и завершать работу при вводе слова "все".

С этого надо было начинать. То есть лексический анализ делать надо. Что не понятно, так это в чем заключается результат анализа. Я лично думаю, что надо просто проверить строку на правильность, но я могу ошибаться.
Еще не понятно, что из себя представляют константа, тип и идентификатор. С точки зрения правил Паскаля на этапе лексического анализа они идентичны. То есть неразличимы.

В качестве примера я прикрепил картинку с другими заданиями и их входными строками. Там у меня не возникает вопросов по поводу входных строк. все итак ясно.

Каким образом верхняя строка соответствует верхней схеме? С нижней вопросов нет.

Отложим пока лексический анализ и займемся синтаксическим. Тогда мы имеем дело с последовательностью лексем. Допустим, что мое предположение верно и константа, тип, идентификатор действительно неразличимы. Пусть им всем соответствует одна лексема I. Тогда твоей схеме будет соответствовать такая грамматика:
S -> IA(B
A -> ,IA
A -> :
B -> I:IC
B -> )
C -> ,IC
C -> )
Этой грамматике будет соответствовать следующий мп-автомат (немного нестандартно я его представил, но общий случай нас не интересует, если надо, можешь построить сам):

По вертикали отложены возможные лексемы. По горизонтали - символы, которые могут быть в магазине.
В самом начале в магазине находится символ S. На каждом шаге автомата мы берем следующую лексему и извлекаем из магазина символ (он при этом удаляется). Далее находим их пересечение в таблице и в зависимости от содержимого ячейки совершаем следующие действия:
- - Ошибка, конец проверки. Это значит, что если мы попали в эту клетку, то строка не соответствует грамматике.
+ - Строка соответствует грамматике, конец проверки.
next - Просто идем дальше
Последовательность символов - вставить все указанные символы в обратном порядке (начиная с последнего), после чего идем дальше. То есть например если в ячейке написано "A(B", вставляем в магазин символы "B", "(", "A".

Устраивает такой автомат? Если есть вопросы давай их сюда =). Если нет, то пойдем дальше. Еще скажи - лексический анализ сам сможешь сделать?