programparser(input, output), label 99;

const empty ~ *; УЯГ sym: char;.

ftoceuxae getsym; begin

repeat read{sym); write{sym) until sym Ф end {getsym) ;

procedure error; begin writeln;

writeln ( INCORRECT INPUT)i goto 99 end {error) ;

procedure term; procedure/<rcor; begin

if sym in [A.. Z, empty] then getsym else if jym = [ tlien begin efcjm; term;

if. sym = T *hen rt5;/n dse error end else error end {factor} ; beginfactor;

while *j;m in [A.. Z,[, e ijp/yl.do/iictor . end {term} ;

procedure expression; begin term;

while sym = , do

begin ge/s>/M; term

end {expression} ;

begin [основная программа} while -\eof(input) do begin getsym;

if sym in [A.. ZJ then getsym else rror;

if л:>т ssr as. then getsym else trror;

лргт/ои;

if jjyffi ?b . then error; writeln; readln; end ; 99: end

1рограмма 5.2. Грамматический разбор для языка (5.12).

языка. Формируемые структуры выдаются как параметпк зультаты соответствующих процедур распознавания язь вых конструкций; таким образом, эти процедуры прев щаются в процедуры трансляции. Естественно, в качес^ результатов передаются не сами структуры, а ссылки них р, q, г (см. рис. на с. 342).

Ясно, что процедура lactor формирует новые элемент структуры данных; остальные же две процедуры связываю* их в линейные списки, при этом term использует для связыв ния поле sue, а expression - иоле alt. Подробности показаны в программе 5.3.

Метод обработки нетерминальных символов нуждается в некотором пояснении. Нетерминальный символ может ветре-титься в качестве фактора раньше, чем появится в левой ч^аети порождающего правила.-Дроцедура {ind{sym, h) ищет заданный символ sym в линейном списке, где собраны все заголовки нетерминальных символов. Если символ найден ссылка на него присваивается h, а если он еще не содержится в этом списке, то добавляется к нему. В процедуре find при меняется метод барьера, подробно обсуждавшийся в гл. 4.

Программа 5.3 состоит из трех частей, каждая обрабатывает определенный раздел входного файла. Часть 1 читает порождающие правила и преобразует их в соответствующие структуры данных. Часть 2 читает и идентифицирует один символ - это начальный символ, с которого начинается порождение предложения языка. (Ему предшествует знак $, разграничивающий части 1 и 2 входных данных.) Часть 3 сть программа грамматического разбора (5.П), читающая входные предложения и. анализирующая их в соответствии со структурами данных, сформированными в части 1.

Примечательно, что программа 5.3 получена просто с помощью включения добавочных операторов в неизмененную программу 5.2. Старая программа только распознавала правильно сформированные предложения, на ее основе можно построить новую, расширенную программу, которая не только распознает, но и транслирует предложения. Такой метод построения процессоров для работы с языком при помоши поэтапного уточнения, или, скорее, поэтапного дополнения, очень полезен. Он позволяет разработчику сосредоточить внимание исключительно на каком-то одном аспекте обработки языка, прежде чем обратиться к другим аспектам, и поэтому облегчает проверку правильности транслятора или, во всяком случае, обеспечивает высокий уровень надежности при раЗ работке программы. В нашем довольно простом примере раЗ работка транслятора состоит из двух этапов. Более сложные языки и более сложные задачи трасляции требуют значительно большего числа отдельных этапов дополнения, Очень

program generaiparser {input, output y, label 99; cimt empty = tyfe pointer =node; hpointer ~ 1 header; node = record sue, alt: pointer;

case terminal: boolean of

. true: (tsym: char);

false: (nsym: hpointer)

end ;

header = тести sym: char;

entry: pointer; .. sue: hpointer

end ;

var list, sentinel, h: hpointer; p: pointer;

sym: char;

ok: boolean;

ftoceume getsym; begin

repeat read(sym); write(sym) mtll sym Ф' aA.{getsym\ ;

ftoceiaTefind(s: char; vat h: hpointer);

{поиск в списке нетерминального символа s, если его нет,

включение его]

var hi: hpointer; begin Al := list; sentinel].sym := s;

while hll.sym s йо hi := hl].suc;

if hi = sentinel then

Ъegin.{включeнue] new (sentinel); hlsuc := sentinel; hl].entry :- nil

end ;

Л := Л1 nd{ ;

procedure error;

begin writeln; -

VfnVe/и (INCORRECT SYNTAX); goto 99 end {error} ;

procedure term (var p,q,r: pointer); var aj),c: pointer; proceduie/ac/or iwtp,q: pointer);