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

[Archon]

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

S -> IA(B
A -> ,IA
A -> :
B -> I:IC
B -> )
C -> ,IC
C -> )

[1147]

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

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

[Archon]

Ну, для начала скажи, что с вас будут требовать. У нас надо было к схеме придумать грамматику, составить мп-автомат и написать прогу. Если у вас хватит того, что есть на твоем примере, то вот автомат:

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

У меня вот что получилось: Грамматика языка: G=({V,N,T}, {S,A,B}, P,S)
S→ NA(B
A→ ,NA
A→ :
B→ V:TC
B→ )
C→ ,V:TC
C→ )

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

[1147]

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

[Archon]

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

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

[1147]

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

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

[1147]

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

[Archon]

Код

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.

[Гость]

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

[Archon]

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

[Гость]

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

[Archon]

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

[Гость]

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