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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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