IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> вопрос по синтаксическому анализу
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 205
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


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

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


Эскизы прикрепленных изображений
Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 205
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


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


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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

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


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Бывалый
***

Группа: Пользователи
Сообщений: 205
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


картинку заменил. писал об одном задании а думал о другом. Ну теперь все верно
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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

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


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


Даже не совсем так. По идее тебе нужна функция, которая из строки выделяет следующую лексему и возвращает ее. Например в таком виде:
Код
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 -


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






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


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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

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

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


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Бывалый
***

Группа: Пользователи
Сообщений: 205
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


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

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

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


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


Эскизы прикрепленных изображений
Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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

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

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


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Бывалый
***

Группа: Пользователи
Сообщений: 205
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


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


Эскизы прикрепленных изображений
Прикрепленное изображение Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Бывалый
***

Группа: Пользователи
Сообщений: 205
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


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


Эскизы прикрепленных изображений
Прикрепленное изображение
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Бывалый
***

Группа: Пользователи
Сообщений: 205
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


и еще никак немогу понять, по каким правилам мы строим верхнюю горизонтальную строку таблицы... почему там только одна скобка, нет запятой например...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Бывалый
***

Группа: Пользователи
Сообщений: 205
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


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

Сообщение отредактировано: 1147 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

Репутация: -  24  +


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


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #19


Бывалый
***

Группа: Пользователи
Сообщений: 205
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


Если проще сделать как в моем примере, то давай сделаем как проще и быстрее
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Бывалый
***

Группа: Пользователи
Сообщений: 205
Пол: Мужской
Реальное имя: Евгений

Репутация: -  0  +


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

Сообщение отредактировано: 1147 -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 9:28
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name