Prolog #6.1-6.2: Парсинг

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

Запомните, что парсинг некоторой грамматики включает в себя два вида активности:

• Проверка на заданный токен
• Проверка еще одной сложной грамматической структуры

Мы разберемся с каждым видом.

6.1 Низкоуровневый парсинг на Prolog

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

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

Задача 9

1. Определите предикат Пролог match/2 используя единичное правило или факт (факт – было бы круто!), который подпадает под определение, которое мы только что дали. Предположим, что первый параметр унифицируется с токеном, а второй, со списком токенов. Предикат может быть использован один из следующих способов:
1. match(if, Tin)
2. match(ident(a), Tin) [Здесть а – это имя идентификатора, полученная из входного потока]
2. Предикат match/2 хорош для проверки каков следующий токен. Но бывает так, что когда вы хотите проверить токен, и затем убрать его из потока. Определите новый предикат eat/3, который будет это делать. Должно легко получиться адаптировать определение match/2 для того, чтобы получить eat/3.

6.2 Высокоуровневый парсинг на Prolog

Рассмотрим следующее определение грамматики для языка FP.

<FnDef> ::= Ident <ParamList> Assign <FnExpDef>

Одним из способов чтения этого правила:

Если входная строка содержит токен Indent и <ParamList> и токен Assign и <FnExpDef> тогда он содержит <FnDef>

Использование “и” подчеркивает конъюнктивную природу правила правой руки для грамматического правила. Похоже, что мы можем немедленно перевести это на язык Prolog.

parseFnDef(..) :-
parseIdent(..),
parseParamList(..),
parseAssign(..),
parseFnExpDef(..).

На самом деле, практически каждое грамматическое правило может быть сведено к клозам Пролога таким образом (более или менее).

Пример 6 – Парсинг if..then..else

Когда парсите более одного токена нельзя полагаться на факты Пролога. Но принцип должен быть тем же самым. Если мы хотим распознать if..then..else выражение, то нам нужно сопоставить начальную часть входного списка и передать часть списка, которая не была частью этого сопоставления. Мы можем рассмотреть следующие Паскального вида выражения и соотвествующий список токенов.

if a then b else c;
x := 5;
[if,ident(a),then,ident(b),else,ident(c),;,ident(x),=,number(’5’),;]

[Обратите внимание, что лексический анализатор сконвертировал := в =]

Теперь то что мы хотим так это некий предикат parseIfThenElse, который будет сопоставлять первые 6 токенов и “возвращать” оставшуюся часть списка как не сопоставленную. Как мы должны определить этот предикат? Ну, факт не поможет, так что надо определять правило. Левая часть будет чем-то вроде этого:

parseIfThenElse(Sin, Sout) :- ...

где Sin унифицируется с исходным списком, а Sout  - со списком после сопоставления выражения if..then..else. Мы можем создать следующий запрос:

| ?- parseIfThenElse([if,ident(a),then,ident(b),else,ident(c),scolon,
ident(x),assign,number(’5’),scolon],X).
X = [;,x,=,5,;] ?
yes

Как насчет правой стороны для правила parseIfThenElse? Эта часть правила должна давать знать, что токен if найден, а также возвращать остаток списка, назовем его X; затем токен а должен быть сопоставлен с головой X, покидая список Y и так далее. Другими словами мы можем сформулировать правило вот так:

parseIfThenElse(Sin,Sout) :-
parseIf(Sin,R),
parseName(R,S),
parseThen(S,T),
parseName(T,U),
parseElse(U,V),
parseName(V,W),
parseEndIf(W,Sout).

Обратите внимание, что когда последний предикат справа разрешается, переменная Sout должна содержать часть списка, которая не распознана.

И конечное соображение по этому примеру. Вы можете интересоваться, где предикат match/2 и eat/3 должны вступить в игру. На самом деле, приведенное выше правило может быть переписано используя eat/3 как показано ниже, т.к каждый предикат сопоставляет единичный токен.

parseIfThenElse(Sin,Sout) :-
eat(if,Sin,R),
eat(ident(_),R,S),
eat(then,S,T),
eat(ident(_),T,U), eat(else,U,V),
eat(ident(_),V,W),
eat(endif,W,Sout).

Конечно, никакое из этих правил не будет полезно в общем случае, так как else и then части сложны в обработке.

 

Задача 10

1. Реализуйте один предикат для парсинга, как показано выше, для следующего грамматического правила.
1. parseFnDef(Tin,Tout) :-
   IDENT <ParamList> ASSIGN <FnExpDef> Убедитесь, что вы правильно используете низко-уровневые предикаты определенные ранее.
2. Реализуйте одно общее правило для parseIfThenElse.

Задача 11

Забавная задача.

Напишите предикат separate, который принимает список токенов и возвращает два списка токенов, в одном все числовые токены входного списка а в другом – все токены идентификаторы из входного списка. Любые другие токены из списка игнорируются. Если файл содержит строку

‘12 + 13 equals twenty five (25)’

тогда мы должны увидеть следующий результат.

?- tokens(’test’,Y), separate(Y,Ids,Nums).
Ids = [id(equals),id(twenty),id(five)]
Nums = [num(’12’),num(’13’),num(’25’)]
Y = [num(’12’),plus,num(’13’),id(equals),id(twenty),id(five),
lp,num(’25’),rp,eof]
Yes

Ваши имена для токенов могут немного отличаться, но должны распознаваться.