Организация синтаксического анализатора
Формы Бэкуса - Наура
Цепочки языка могут содержать метасимволы, имеющие особое назначение. Метаязык, предложенный Бэкусом и Науром (БНФ) использует следующие обозначения:
символ «::=» отделяет левую часть правила от правой (читается: «определяется как»);
нетерминалы (синтаксическая категория) обозначаются произвольной символьной строкой, заключенной в угловые скобки «<» и «>»;
терминалы - это символы, используемые в описываемом языке; правило может определять порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты «|» (читается: «или».
Для повышения удобства и компактности описаний, в расширенных БНФ вводятся следующие дополнительные конструкции (метасимволы):
квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;
фигурные скобки «{» и «}» означают повторение заключенной в них синтаксической конструкции ноль или более раз;
сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз;
круглые скобки «(» и «)» используются для ограничения альтернативных конструкций.
Пример. Правила, определяющие понятие «идентификатор» некоторого языка программирования, будут выглядеть следующим образом:
<буква> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<идентификатор> ::= <буква> { (<буква> | <цифра>) }
Построить синтаксический анализатор для понятия простое-выражение:
VAR c: char; b:boolean;
PROCEDURE REWRI;
Begin
if t then
begin
read(c);
write(c);
end;
End;
PROCEDURE ERROR (k: word);
Begin
writeln;
Case k of
1: writeln(нет баланса скобок);
2: writeln(не целое без знака);
3: writeln(неверная операция);
4: writeln(лишние символы);
end;
t := false;
End;
PROCEDURE ZN;{проверка знака}
Begin
if t and not(c in [‘-’,’+’,’*’,’/’]) then error (3);
End;
PROCEDURE ZIF;
Begin
if t then
if (c < ‘0’) or (c>’9’) then error (2)
else while (c >= ‘0’) and (c<=’9’) and not eoln do
rewri;
End;
PROCEDURE PSK;{ правая скобка}
Begin
if t then
if c<> ‘)’ then error (1)
else REWRI;
End;
PROCEDURE PRV;{простое выражение}
Begin
if t then
if c = ‘(’ then
begin REWRI; PRV; ZN; REWRI; PRV; PSK; end
else
ZIF;
End;
Begin
T:= True;
If eoln then writeln (‘нет выражения’)
else begin
REWRI; PRV; if t and (c<> #13) then ERROR(4) end;
End.