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

[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".

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

[1147]

Синтаксические анализаторы регулярных языков на вход получают строку лексем. В процессе синтаксического анализа происходит распознавание конструкций языка в строке токенов. Тоесть в данном случае, на вход будут поступать лексемы, записанные в таблице. Программа должна проверять на ошибки. Последовательность СИМВОЛОВ, а не СЛОВ-нет ли пропусков, местами не перепутаны ли они,правильно ли написаны символы (та ли буква) и т.д. Ошибки в словах искать не нужно-это очень сложно. Так что по-моему лексический анализ здесь ненужен.
Насчет верхней строки и схемы-я опять перепутал. К сообщению прикрепил верный пример.
По поводу неразличимости константы и идентификатора я согласен. А вот тип должен быть одним из следующих: integer, word, single, double. Значит и в таблицу, насколько я понимаю, нужно внести изменения.
Также я добавляю пример синтаксического анализатора. Там идентификатор представляет собой несколько символов, или символы и цыфры. (тоесть не обязательно что константа и идентификатор-идентичны).
Вопрос у меня следующий: на схеме моего задания константа и идентификатор обозначены словами, а в примере синтаксического анализатора который я прикрепил они обозначены V и N. Это одно и тоже, просто разница в обозначении, или всетаки тут имеются ввиду разные вещи?
А вообще основная проблема у меня заключается в написании этого задания на паскале.
Автомат этот меня вполне устраивает (лишь бы делал все правильно, так что можем двигаться дальше.

[1147]

Я тут приблизительно составил таблицу с учетом типа и идентификатора. Но мне непонятен принцип построения грамматики, откуда берутся символы: S, A, B, C, и почему тому или иному символу соответствует - ( или IA(B например, почему А,В,С используются по 2 раза, а S-один. Поэтому завершить таблицу несмог...
Еще я хотел бы уточнить насчет того что имеется ввиду под понятием токен...
Например, дано выражение: If Sum>5 then pr:=true;
Так вот, If, Sum, >, 5, then, pr, :=, true- это все лексемы (кстати, у меня в методичке лексема Sum обозначена как идентификатор).
Тогда токен, как я понимаю-это, если взять лексему Sum например, это каждый символ составляющий лексему, т.е. s, u, m. Так? Данная лексема содержит в себе 3 токена, если я правильно понял?