Диаграмма состояний

Грамматика у нас рекурсивная, следовательно, можно распознавать без конечной цепочки символов.

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

1. При каждом разветвлении синтаксического графа должен быть обеспечен однозначный выбор ветви, по которой будет идти дальнейший разбор, по символу, с которого начинается эта ветвь.

2. Если в синтаксическом графе есть подграфы А, которые можно пройти не читая никаких входных символов, то такая нулевая ветвь должна помечаться всеми символами (литерами), которые могут следовать за А.

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

Формальный переход от синтаксического графа к программе происходит по следующим правилам:

1). Свести систему графа к минимальному числу последних, используя соответствующие правила подстановки.

2). Преобразовать исходный граф в программу следующими эквивалентными заменами:

1.

begin P(A); P(B); P(C); end;

2.

Допустим, что символ со сканера находится в переменной ch, аLi -это множество начальных символов в конструкции А, В, С.

Case ch of

L1: P(A);

L2: P(B);

L3: P(C);

End;

Или же

If ch in L1 then

P(A) else

If ch in L2 then

P(B) else

If ch in L3 then

P(C) else Error;

3.

While ch in L do P(A);

4.

if ch = 'x' then read(ch) else Error;

Программа совмещающая эти функции:

Program sint;

Var ch: char;

Procedure A;

Begin

If ch = 'x' then read(ch) else

If ch = '(' then

begin

read(ch); A;

while ch = '+' do

begin read(ch); A; end;

if ch = ')' then read(ch) else Error;

end else Error;

end;

begin

read(ch); A;

end.

Правила, которые формально определяются следующими правилами:

1. Всякая переменная или константа есть выражение.

2. Если ₁ знак одномерной операции, авыражение, то запись₁ или₁ есть выражение.

3. Если ₂ знак двуместной операции, авыражения, то₂ или₂ есть выражения и т.д._n ...n и...n _{n .}

4. Других выражений не существует.

Пример:

АВ  АВ

А  В + С  АВ  С +

А  (В + С / D)  ABCD / + 

A  B + C  D  AB  CD  +

Правила перевода инфиксной записи в польскую:

1. Идентификаторы или операнды польской записи следуют в том же порядке, что и в инфиксной.

2. Операторы польской записи следуют в том порядке, в каком они должны вычисляться (слева направо).

3. В постфиксной записи операторы располагаются непосредственно за своими операндами.

4. Унарный минус (-В) может быть записан в двух формах либо 0-В либо @B.

A+ (-B+CD)AB@CD+ +

Вычисление арифметических выражений в интерпретаторах:

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

Вычисления строятся следующим образом:

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

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

3. Если сканируемый символ унарный оператор, то он применяется к верхнему операнду в стеке, который и заменяется на полученный результат.

Пример:

Преобразуем постфиксную запись AB@CD*++ в инфиксную

Цепочка символов	Старое состояние стека	Правило	Новое состояние стека
AB@CD*++ B@CD*++ @CD*++ CD*++ D*++ *++ ++ +	- А A | B A | -B A | -B | C A | -B | C | D A | -B | C * D A | -B + C * D	1 1 3 1 1 2 2 2	A A | B A | -B A | -B | C A | -B | C | D A | -B | C * D A | -B + C * D A + -B + C * D

Вычисление математических выражений в компиляоре

В компиляторе мы должны прийти к командам, вычисляющим эти выражения.

А ВАВ

, А, В, Т

А В + СDABCD+

, A,B,T1

, C,D,T2

+, T1,T2,T

Такая форма называется запись в виде тетрад.

Более современным, является преобразование в треады.

А В + СDABCD+

1. ,A,B

2. ,C,D

3. +, (1), (2)