Prolog #6.3: Парсинг

6.3. Парсинг выражений

Распространенной задачей в парсинге является обработка альтернатив. Мы можем увидеть эту задачу а также поработать с более сложными грамматиками реализуя парсер для простых арифметических выражений. Напомним следующие грамматические правила для выражений.

Exp ::= Term { ’+’ Term } | Term { ’-’ Term }
Term ::= Factor { ’*’ Factor } | Factor { ’/’ Factor }
Factor ::= number | ident | ’(’ Exp ’)’

Эта грамматика может быть записана более понятным образом вот так:

Exp ::= Term ExpTail
ExpTail ::= empty | ’-’ Term | ’+’ Term
Term ::= Factor TermTail
TermTail ::= empty | ’*’ Factor | ’/’ Factor
Factor ::= number | ident | ’(’ Exp ’)’

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

exp(Tin, Tout) :- Term(Tin,X), expTail(X,Tout).

expTail(Tin, Tin) :- .

expTail(Tin, Tout) :- eat(plus,Tin,X), term(X,Tout).
expTail(Tin, Tout) :- eat(minus,Tin,X), term(X,Tout).
term(Tin, Tout) :- factor(Tin,X), termTail(X,Tout).

termTail(Tin, Tin) :- .
termTail(Tin, Tout) :- eat(mult,Tin,X), factorX,Tout).
termTail(Tin, Tout) :- eat(div,Tin,X), factorX,Tout).
factor(Tin, Tout) :- eat(number(_),Tin,Tout).
factor(Tin, Tout) :- eat(ident(_),Tin,Tout).
factor(Tin, Tout) :- eat(lp,Tin,X),exp(X,Y),eat(rp,Y,Tout).

Задача 12

Реализуйте парсер описанный выше и запустите его на файле, в котором есть выражение – сделайте это несколько раз чтобы убедиться (убедить себя :-) ) что парсер работает. Заметьте, что в этой задаче вы использовали лексический анализатор для FP чтобы реализовать парсер для языка, не связанного с FP.

6.4 Парсер опциональных структур (необязательных)

Одной из особенностей выражения выбора является то, что часть else необязательна. Как мы должны поступать с необязательными частями? На самом деле, мы просто можем записать вид грамматического правила, как есть. Например, если мы напишем грамматическое правило выбора вот так:

<IfElse> ::= IF <Bexp> THEN <FnExp> <ElsePart> ENDIF

Соответствующие предикаты Пролог могут иметь следующий вид.

parseIfElse(Sin,Sout) :-
eat(if,Sin,R),
parseBexp(R,S),
eat(then,S,T),
parseFnExp(T,U),
parseElsePart(U,V),
eat(endif,V,Sout).

parseElsePart(Sin,Sout) :-
eat(else,Sin,R),
parseFnExp(R,Sout).
parseElsePart(Sin,Sin). %% делает эту часть необязательной.

Другой формой необязательного парсинга появляется когда токен может начинаться более чем с одной фразы. Это появляется в выражении определения функции, когда идентификатор может быть один, а может быть с параметрами. И мы снова можем записать грамматические правила и затем напрямую транслировать их в Пролог. Следующее правило это сокращенная версия грамматического правила для определения функций в FP.

<FnExp> ::= NUMBER |
IDENT |
IDENT <TermList>

А это Пролог:

parseFnExp(Sin,Sout) :-
eat(number,Sin,Sout).
parseFnExp(Sin,Sout) :-
eat(ident(_),Sin,Sout).
parseFnExp(Sin,Sout) :-
eat(ident(_),Sin,R),
parseTermList(R,Sout).

Задача 13

Теперь, используя техники описанные выше, реализуйте множество предикатов парсинга для FP грамматик. Протестируйте после реализации.

<Program> ::= <FnDefList> PERIOD

<FnDefList> ::= <FnDef> |
<FnDef> SCOLON <FnDefList>

<FnDef> ::= IDENT <ParamList> ASSIGN <FnExpDef>
<FnExpDef> ::= <FnExp> |
let <FnDefList> in <FnExp>

<ParamList> ::= IDENT |
IDENT <ParamList>

<FnExp> ::= NUMBER |
IDENT |
<FnApp> |
<Selection>

<Selection> ::= if <BExp> then <FnExp> [<ElsePart>] endif

<ElsePart> ::= else <FnExp>

<BExp> ::= <FnExp> <CompOp> <FnExp>

<CompOp> ::= LT | LE | GT | GE | EQ | NE

<FnApp> ::= <FnName> <TermList>

<FnName> ::= IDENT | ADD | SUBT | MULT | DIV | MOD

<TermList> ::= <Term> |
<Term> <TermList>

<Term> ::= NUMBER |
IDENT |
LP <FnExp> RP