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

[1147]

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

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

[Archon]

Судя по всему тебе нужна программа, принимающая строку и определяющая, удовлетворяет ли она грамматике, заданной в условии. Непонятно 2 вещи:
1 Раз уж ты заговорил о таблице переходов, значит решение "в лоб" тебе не подходит и сделать нужно автомат. А какой автомат, МП?
2 В какой форме приходят "идентификаторы" и "варианты". Ести это уже распознанные лексемы (токены), то все просто, а вот если их тоже надо распозновать, то возникает вопрос посредством чего это делать.

[1147]

Мне кажется что это контекстно-свободные грамматики, значит нужен автомат с магазинной памятью. Я сомневаюсь между МП и конечными. А входная строка, надо полагать, к примеру будет выглядеть так: var a: integer, b:real. Но возможно я и ошибаюсь. Варианты и идентификаторы мне кажется приходят в виде токенов. так как считается что строка токенов уже была получена при лексическом разборе и в дальнейшем будет зашита в программу
А что вообще подразумевается под идентификаторами и вариантами?

[Archon]

Похоже, ты прикрепил не ту картинку =) Проверь.

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

[1147]

картинку заменил. писал об одном задании а думал о другом. Ну теперь все верно

[Archon]

Если лексемы уже выделены, то значит в строке присутствуют нетерминальные символы, например:
"<константа>,<константа>,<константа>:(<тип>:<идентификатор>,<идентификатор>,<идентификатор>)"
, где <константа>, <тип> и <идентификатор> - нетерминальные символы.

Добавлено через 1 мин.
PS Мы делали на МП-автоматах.

[Archon]

Даже не совсем так. По идее тебе нужна функция, которая из строки выделяет следующую лексему и возвращает ее. Например в таком виде:

Код

const
    // Возможные лексемы (для мп-автомата это - набор терминальных символов):
    tCONSTANT = 0; // константа
    tCOMA     = 1; // запятая
    tCOLON    = 2; // двоеточие
    tLBRACKET = 3; // левая скобка
    tRBRACKET = 4; // правая скобка
    tTYPE     = 5; // тип
    tIDENT    = 6; // идентификатор
    tEND      = 7; // конец строки

type
    Token = record
        Lex: integer;  // Лексема, соответствующая этому токену
        Value: string; // Ее значение
    end;

function GetNextToken: Token;
begin
    // ...
end;

Если тебе надо только синтаксическую проверку, то значение нас не интересует, тогда GetNextToken будет возвращать сразу соответствующую константу:

Код

function GetNextToken: integer;
begin
    // ...
end;

Далее идет реализация собственно мп-автомата. Нужна с этим помощь?

Сообщение отредактировано: Archon - 26.11.2008 21:50

[Гость]

Да, помощь с автоматом мне бы не помешала!
И еще я не могу понять какая строка будет на входе автомата? насчет var a:integer, b:real я правильно предположил, или здесь будет чтото другое. Я вообще непонимаю само задание: синтаксический анализ: "вариант". что подразумевается под вариантом, что будет анализировать автомат и как будет выглядеть алфавит языка?

[Archon]

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

А как выглядит задание слово в слово? Может быть "вариант" - это название задания? Или там номер варианта дальше следует? Или это написано на бумажке с "одним из вариантов" задания?

И еще я не могу понять какая строка будет на входе автомата? насчет var a:integer, b:real я правильно предположил, или здесь будет чтото другое.

Что именно будет на входе я не знаю. Лучше уточнить у преподавателя. Могу предположить, что что-то вроде "константа,константа,константа: (тип:идентификатор,идентификатор,идентификатор)". Или может быть "const123, abc:(my_type:i,j,test24,test25)". Но твоя строка точно не подходит, потому-что она не удовлетворяет грамматике, заданной в схеме. То есть она может прийти, но мы должны будем сказать, что она ошибочна.

Да, помощь с автоматом мне бы не помешала!

Ок, я напишу реализацию мп-автомата, но наверно только завтра.

Сообщение отредактировано: Archon - 28.11.2008 17:03

[Archon]

Кстати, прежде чем писать автомат, надо определиться с грамматикой. С этим тебе тоже нужна помощь?

[1147]

задание выглядит так:
Разработать программу, которая выполняет лексический и синтаксический анализ в соответствии с заданной синтаксической диаграммой. Программа должна обеспечивать многократный ввод предложений, их об-работку с выводом на экран результатов лексического и синтаксического анализов и завершать работу при вводе слова "все".
Дальше следует мой вариант со схемой. Входная строка возможно будет такой:
a,b,c:()
или такой:
x:(pr:array)

хотя я непонимаю что это за конструкция и для чего используется....

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


Сообщение отредактировано: 1147 - 28.11.2008 19:56

[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 токена, если я правильно понял?

[1147]

и еще никак немогу понять, по каким правилам мы строим верхнюю горизонтальную строку таблицы... почему там только одна скобка, нет запятой например...

[1147]

------------

Сообщение отредактировано: 1147 - 2.12.2008 11:01

[Archon]

Синтаксические анализаторы регулярных языков на вход получают строку лексем. В процессе синтаксического анализа происходит распознавание конструкций языка в строке токенов. Тоесть в данном случае, на вход будут поступать лексемы, записанные в таблице. Программа должна проверять на ошибки. Последовательность СИМВОЛОВ, а не СЛОВ-нет ли пропусков, местами не перепутаны ли они,правильно ли написаны символы (та ли буква) и т.д. Ошибки в словах искать не нужно-это очень сложно. Так что по-моему лексический анализ здесь ненужен.

Тогда пиши функцию, которая возвращает следующую лексему. Как GetNextToken в сообщении №7.

Вопрос у меня следующий: на схеме моего задания константа и идентификатор обозначены словами, а в примере синтаксического анализатора который я прикрепил они обозначены V и N. Это одно и тоже, просто разница в обозначении, или всетаки тут имеются ввиду разные вещи?

Это одно и то же.

Я тут приблизительно составил таблицу с учетом типа и идентификатора. Но мне непонятен принцип построения грамматики, откуда берутся символы: S, A, B, C, и почему тому или иному символу соответствует - ( или IA(B например, почему А,В,С используются по 2 раза, а S-один. Поэтому завершить таблицу несмог...

Смотри грамматику. S - это просто начальный нетерминальный символ. A, B, C - тоже нетерминальные символы, названия от фонаря. Для чего введены? Смотри грамматику =) Кстати, в твоем примере не мп-автомат, а недетерминированный конечный. Если хочешь, можем сделать аналогично твоему примеру, будет даже проще.

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

Нет, токен - это синоним лексемы. Во всяком случае я это так понимаю =)

PS Подробности потом, сейчас я спать ложусь

[Archon]

Так через какой автомат делать будешь? МП или как в примере?

[1147]

Если проще сделать как в моем примере, то давай сделаем как проще и быстрее

[1147]

А где можно посмотреть эту грамматику? Не знаешь какой-нибудь литературы по этому поводу? может посоветуешь что?

Сообщение отредактировано: 1147 - 3.12.2008 21:17