Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ вопрос по синтаксическому анализу

Автор: 1147 26.11.2008 21:48

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


Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: Archon 26.11.2008 23:09

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

Автор: 1147 26.11.2008 23:24

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

Автор: Archon 27.11.2008 0:09

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

Автор: 1147 27.11.2008 0:28

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

Автор: Archon 27.11.2008 0:36

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

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

Автор: Archon 27.11.2008 1:47

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

Код
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;

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

Автор: Гость 28.11.2008 4:11

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

Автор: Archon 28.11.2008 20:43

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

А как выглядит задание слово в слово? Может быть "вариант" - это название задания? Или там номер варианта дальше следует? Или это написано на бумажке с "одним из вариантов" задания?
Цитата
И еще я не могу понять какая строка будет на входе автомата? насчет var a:integer, b:real я правильно предположил, или здесь будет чтото другое.
Что именно будет на входе я не знаю. Лучше уточнить у преподавателя. Могу предположить, что что-то вроде "константа,константа,константа: (тип:идентификатор,идентификатор,идентифик
атор)". Или может быть "const123, abc:(my_type:i,j,test24,test25)". Но твоя строка точно не подходит, потому-что она не удовлетворяет грамматике, заданной в схеме. То есть она может прийти, но мы должны будем сказать, что она ошибочна.
Цитата
Да, помощь с автоматом мне бы не помешала!
Ок, я напишу реализацию мп-автомата, но наверно только завтра.

Автор: Archon 28.11.2008 21:06

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

Автор: 1147 28.11.2008 23:54

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

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

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



Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: Archon 2.12.2008 1:35

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

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

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

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

Автор: 1147 2.12.2008 4:10

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


Эскизы прикрепленных изображений
Прикрепленное изображение Прикрепленное изображение

Автор: 1147 2.12.2008 10:00

Я тут приблизительно составил таблицу с учетом типа и идентификатора. Но мне непонятен принцип построения грамматики, откуда берутся символы: 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 2.12.2008 11:02

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

Автор: 1147 2.12.2008 14:59

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

Автор: Archon 3.12.2008 5:43

Цитата
Синтаксические анализаторы регулярных языков на вход получают строку лексем. В процессе синтаксического анализа происходит распознавание конструкций языка в строке токенов. Тоесть в данном случае, на вход будут поступать лексемы, записанные в таблице. Программа должна проверять на ошибки. Последовательность СИМВОЛОВ, а не СЛОВ-нет ли пропусков, местами не перепутаны ли они,правильно ли написаны символы (та ли буква) и т.д. Ошибки в словах искать не нужно-это очень сложно. Так что по-моему лексический анализ здесь ненужен.
Тогда пиши функцию, которая возвращает следующую лексему. Как 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 3.12.2008 22:23

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

Автор: 1147 3.12.2008 23:17

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

Автор: 1147 4.12.2008 1:17

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

Автор: Archon 4.12.2008 16:13

Дак я ее написал в своем посте:

Цитата
S -> IA(B
A -> ,IA
A -> :
B -> I:IC
B -> )
C -> ,IC
C -> )


Автор: 1147 4.12.2008 16:56

вопрос с литературой можно оставить..
У меня вот что получилось: Грамматика языка: G=({V,N,T}, {S,A,B}, P,S)
S→ NA(B
A→ ,NA
A→ :
B→ V:TC
B→ )
C→ ,V:TC
C→ )
можем мы взять за основу эту грамматику чтобы построить таблицу (я к сожалению так и не понял как ее строить, объясни пожалуйста как формируется горизонтальная строка) и затем автомат? Потому что на обсуждение других вопросов уже нет времени...

Автор: Archon 5.12.2008 0:24

Ну, для начала скажи, что с вас будут требовать. У нас надо было к схеме придумать грамматику, составить мп-автомат и написать прогу. Если у вас хватит того, что есть на твоем примере, то вот автомат:
Прикрепленное изображение
Это не МП-автомат, а вообще какой-то недетерминированный, но для твоих целей удобный. По горизонтали - лексемы. По вертикали - состояния. На схеме отмечены какой позиции, какое состояние соответствует. На каждом шаге берем следующую лексему, и в зависимости от текущего состояния находим клетку. е - ошибка, к - все нормально, конец проверки. число - переход в новое состояние. Программа для реализации такого автомата элементарна и записана у тебя в примере.

Цитата
У меня вот что получилось: Грамматика языка: G=({V,N,T}, {S,A,B}, P,S)
S→ NA(B
A→ ,NA
A→ :
B→ V:TC
B→ )
C→ ,V:TC
C→ )
Грамматика правильная за исключением набора терминальных символов - туда следует добавить знаки препинания. Только в примере автомат строится сразу, обходя этап построения грамматики. Поэтому сам решай, нужна ли она тебе вообще.

Автор: 1147 5.12.2008 0:33

да вот и я не понимаю зачем вообще нужна эта грамматика. Для чего ее составляют? Она как то используется в программе?
На помощь в написании программы я могу расчитывать?

Автор: Archon 5.12.2008 0:41

Если с вас грамматику не требуют, то просто забудь о ней. Составляют её для порядка, чтоб была =). Считается, что МП-автомат с ней построить проще. Но раз уж мы решили не использовать МП-автомат то я не вижу смысла составлять грамматику. Если тебе всё равно интересно, то я объясню, как на основе такой грамматики построить МП-автомат.

На помощь в написании программе ты расчитывать конечно можешь =)

Автор: 1147 5.12.2008 0:42

А вообще требования к заданию у нас такие же как были и у вас. Составить грамматику->автомат->программу.

Добавлено через 3 мин.
Да, мне было бы интересно узнать как на основе такой грамматики построить МП-автомат.

Автор: 1147 6.12.2008 18:41

хотя на это уже нет времени... помоги пожалуйста написать программу для конечного автомата по последней таблице и все

Автор: Archon 7.12.2008 3:55

Код
const
    a: array[1..7, 1..6] of integer = (
        (2, 8, 8, 8, 8, 8),
        (8, 8, 3, 1, 8, 8),
        (8, 8, 8, 8, 4, 8),
        (8, 5, 8, 8, 8, 9),
        (8, 8, 6, 8, 8, 8),
        (7, 8, 8, 8, 8, 8),
        (8, 8, 8, 6, 8, 9)
    );

function Decode(c: char): integer;
begin
    case c of
        'I': Decode := 1;
        'T': Decode := 2;
        ':': Decode := 3;
        ',': Decode := 4;
        '(': Decode := 5;
        ')': Decode := 6;
    end;
end;

var
    s: string;
    state, i: integer;
begin
    Write('Введите строку для анализа: ');
    ReadLn(s);
    state := 1;
    for i := 1 to Length(s) do begin
        state := a[state, Decode(s[i])];
        if state = 8 then Break;
    end;
    if state = 9 then
        WriteLn('Строка верна')
    else
        WriteLn('Строка ошибочна');
end.

Автор: Гость 7.12.2008 22:57

Как должна выглядеть входная строка чтобы программа выдала сообщение что она верна?? Вот например я ввожу корректную строку: a:(), но программа считает ее невернойsad.gif

Автор: Archon 8.12.2008 1:43

Ну конечно. Она реализует строго тот автомат, что я привел в таблице выше. Все допустимые символы прописаны в ее верхней строке. Таким образом, правильной строкой будет например: I,I,I:(T:I,I,I). То есть идентификаторы и тип свернуты в соответственно I и T. Если хочешь, чтобы программа сама распознавала идентификаторы вроде a, b, c1, test00 и т.п., а также типы вроде integer, double и другие, надо добавить в нее лексический анализатор.

Автор: Гость 8.12.2008 2:33

Ты мог бы это сделать?!? сам я точно не успею-вторник крайний срок сдачи

Автор: Archon 8.12.2008 3:09

Ну уж нет. И так все уже за тебя сделал. К тому же, не ясно, каким образом проводить лексический анализ. Тоже через автоматы? В любом случае, попробуй сделать сам. Я подскажу, если что не получится. Если обобщить, то тебе нужна функция, которая берет на вход строку типа "ident1,a,x,abc000:(integer:int1,int2,temp)" и возвращает эту же строку со свернутыми лексемами: "I,I,I,I:(T:I,I,I)".

Автор: Гость 15.12.2008 21:39

Archon, программу я сдал наконец-то. Хочу выразить тебе благодарность за неоценимую помощь. Один бы я не справился. Кроме того эта тема, как мне кажется, очень полезна для форума, т.к. она единственная где так подробно разбирается синтаксический анализатор.
Большое спасибо! good.gif