Построение парсера в прологе

Question

Я пытаюсь создать парсер, но я не могу понять, как он работает. Мне нужна помощь, когда кто-то укажет мне в правильном направлении, чтобы я мог забрать его оттуда.

У меня есть токенизатор и лексер.

Tokenizer выход:

[INT, добавить, (, INT, A ,,, INT, б, в), =, а, +, б, Int, letin, (, INT, а,), =, пусть, б, =, 10, в, добавить, (, А ,,, Ь,), INT, равным, (, Int, A ,,, INT, б,), =, если, а, == , b, then, letin, (, a,), else, 1, int, main, (, int, input,), =, equal, (, input ,,, 2,)]

Lexer Output:

[TYPE_INT, ИДЕНТИФИКАТОР, OPEN_P, TYPE_INT, ИДЕНТИФИКАТОР, зАПЯТАЯ, TYPE_INT, ИДЕНТИФИКАТОР, CLOSE_P, ASSIGN, ИДЕНТИФИКАТОР, ARITH_ADD, ИДЕНТИФИКАТОР, TYPE_INT, ИДЕНТИФИКАТОР, OPEN_P, TYPE_INT, ИДЕНТИФИКАТОР, CLOSE_P, ASSIGN, LET, ИДЕНТИФИКАТОР, ASSIGN , IDENTIFIER, LET_IN, IDENTIFIER, OPEN_P, IDENTIFIER, COMMA, IDENTIFIER, CLOSE_P, TYPE_INT , ИДЕНТИФИКАТОР, OPEN_P, TYPE_INT, ИДЕНТИФИКАТОР, ЗАПЯТАЯ, TYPE_INT, ИДЕНТИФИКАТОР, CLOSE_P, ASSIGN, COND_IF, ИДЕНТИФИКАТОР, LOGIC_EQ, ИДЕНТИФИКАТОР, COND_THEN, ИДЕНТИФИКАТОР, OPEN_P, ИДЕНТИФИКАТОР, CLOSE_P, COND_ELSE, целочисленный, TYPE_INT, ИДЕНТИФИКАТОР, OPEN_P, TYPE_INT, ИДЕНТИФИКАТОР , CLOSE_P, ASSIGN, IDENTIFIER, OPEN_P, IDENTIFIER, COMMA, INTEGER, CLOSE_P]

Теперь мне нужно построить парсер. Я не понимаю, как начать и как включать параметризованные конструкции.

Мои правила должны быть примерно такими.

program --> functionList. 
functionList --> function,functionListCollection. 
functionListCollection --> functionList | []. 
function --> typeID(typeIdList),[=],expression. 
typeID --> [int],[id] | [bool],[id]. 
typeIdList --> typeID,typeIdListCollection. 
typeIdListCollection --> [,], typeIdList | []. 
expression --> [if], comparison, [then], value, [else], value. 
expression --> [let],[id],[=], value, [in], expression. 
expression --> value, extraExpression. 
extraExpression --> arithmetic | []. 
arithmetic --> [+], value | [-], value. 
comparison --> value, comparisonRight. 
comparisonRight --> [=],[=],value. 
comparisonRight --> [!], [=], value. 
comparisonRight --> [>], value. 
comparisonRight --> [>], [=], value. 
value --> [number]. 
value --> [id], valueParameters. 
valueParameters --> [(],parameters,[)]. | []. 
parameters --> value, parametersList. 
parametersList --> [,], parameters | []. 

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

Answer 1

Ваш «Lexer Output» кажется не только бесполезным, но и опасным. Он (произвольно?) Переименовывает важные символы (например, int), которые уже являются частью анализатора (btw, tokenizer и lexer: синонимы afaik).Так, только кормить DCG (раз исправлен, смотри ниже) с выходом Tokenizer:

tokens_test :- 
    Tokens = [ 
     int,add,=,a,+,33 
     % ...more source code to test - but please use writeq to show it ... 
     %,int,let,in,'(',int,a,')',=,let,b,=,10 
     %,in,add,'(',a,',',b,')',int,equal,'(',int,a,',',int,b,')',= 
     %,if,a,==,b,then,let,in,'(',a,')',else,1 
     %,int,main,'(',int,input,')',=,equal,'(',input,',',2,')' 
    ], phrase(program, Tokens). 

?- tokens_test. 
true 

Я изменил свой DCG, так как у вас [ID] и [число] в качестве терминалов:

id --> [I], {atom(I)}. 
number --> [N], {number(N)}. 

program --> functionList. 
functionList --> function,functionListCollection. 
functionListCollection --> functionList | []. 
function --> typeID,[=],expression. 
typeID --> [int],id | [bool],id. 
typeIdList --> typeID,typeIdListCollection. 
typeIdListCollection --> [,], typeIdList | []. 
expression --> [if], comparison, [then], value, [else], value. 
expression --> [let], id, [=], value, [in], expression. 
expression --> value, extraExpression. 
extraExpression --> arithmetic | []. 
arithmetic --> [+], value | [-], value. 
comparison --> value, comparisonRight. 
comparisonRight --> [=],[=],value. 
comparisonRight --> [!], [=], value. 
comparisonRight --> [>], value. 
comparisonRight --> [>], [=], value. 
value --> number. 
value --> id, valueParameters. 
valueParameters --> ['('],parameters,[')'] | []. 
parameters --> value, parametersList. 
parametersList --> [,], parameters | []. 

Где у вас есть разделитель (запятая, ниже), вы можете избежать службы предикаты как

typeIdList --> typeID,typeIdListCollection. 
typeIdListCollection --> [,], typeIdList | []. 

, которые могут быть

typeIdList --> typeID, ([,], typeIdList | []). 

, но удобство этого «упрощения» может зависеть от других факторов.

как включить параметризованную конструкцию

идентификатора // 0 и число //-не имели терминалы, которые должны «получить обратно» свое значение: они становятся идентификатором // 1 и числа // 1, и обычно, мы использовали для «тега» значение с не терминал (так мы пощадить символы :-)

id(id(I)) --> [I], % better to filter out keywords here... 
    {atom(I), \+memberchk(I,[let, etc etc])}. 
number(number(N,integer)) --> [N], {integer(N)}. 
number(number(N,float)) --> [N], {float(N)}. 

теперь, где они называются, мы должны изменить, чтобы

... 
typeID --> [int],id(_) | [bool],id(_). 
... 

это очевидно, что TypeID // 0 должен теперь «вернуться» значения (так называемые семантические атрибуты), в противном случае они будут потеряны:

... 
typeID(typeID(T,I)) --> [int],id(I),{T=int} | [bool],id(I),{T=bool}. 
... 

, который показывает лучший способ записи TypeID // 1. Может быть

typeID(typeID(T,I)) --> type(T),id(I). 

type(int) --> [int]. 
type(bool) --> [bool]. 

Надеются, что вы получите картину :-)

Answer 2

сделать свой вывод лексический (*) для вас, а не данные, как

[type(int), id(add), open_p, type(int), id(a), ..... 

поэтому вы имеете полную информацию в ваших правилах, как

.... 
typeID(T,A) --> [type(T)], { memberchk(T, [int,bool]) }, [id(A)], 
.... 

Тестирование:

32 ?- phrase(typeID(X,Y), [type(int), id(i)], []). 
X = int, 
Y = i. 

33 ?- phrase(typeID(X,Y), [type(bool), id(i)], []). 
X = bool, 
Y = i. 

34 ?- phrase(typeID(X,Y), [type(float), id(i)], []). 
false. 

(*) Или вы можете просто объединить свои токены и текущий выходной лексер, чтобы получить комбинированные данные, с maplist.