Как написать парсер в прологе для вывода дерева разбора - PullRequest
Новая
       12

Как написать парсер в прологе для вывода дерева разбора

0 голосов
/ 25 января 2019

Я пишу парсер в прологе, который должен уметь анализировать эту математическую формулу:

a = 1 * 2 + (3 - 4) / 5;

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

 PARSE TREE:
 assignment
    ident(a)
    assign_op
    expression
        term
            factor
                int(1)
            mult_op
            term
                factor
                    int(2)
        add_op
        expression
            term
                factor
                    left_paren
                    expression
                        term
                            factor
                                int(3)
                        sub_op
                        expression
                            term
                                factor
                                    int(4)
                    right_paren
                div_op
                term
                    factor
                        int(5)
    semicolon

У меня есть эта функция, которая распечатывает дерево разбора, когда я запускаю код run('program1.txt', 'myparsetree1.txt'). который будет читать математическую формулу из файла program1.txt и распечатывать дерево разбора в файле myparsetree1.txt.

До сих пор я пытался написать эту грамматику для синтаксического анализатора, но не работает, так как я продолжаю получать ошибки существования и создания экземпляров, в основном с letter_code и digit_code из tokenizer, тогда как prolog жалуется на слишком мало аргументов в это среди прочего. 

 /*Loads the tokenizer*/
:- [tokenizer].

parse(I) --> assign(I).
assign(assign(I,'=', Expr,';')) -->
        letter_code(I), '=', expr(Expr), ';'.
expr(expr(Term, add_op, Expr)) -->
        term(Term), add_op, expr(Expr).
expr(expr(Term, sub_op, Expr)) -->
        term(Term), sub_op, expr(Expr).
expr(expr(Term)) --> term(Term).        

term(term(Factor, mul_op, Term)) -->
        factor(Factor), mul_op, term(Term). 
term(term(Factor, div_op, Term)) -->
        factor(Factor), div_op, term(Term).
term(term(Factor)) --> factor(Factor).



factor(factor('(', Expr, ')')) --> '(', expr(Expr), ')'.

factor(factor(Digit)) --> digit_code(Digit).

add_op --> ['+'].       
sub_op --> ['-'].
mul_op --> ['*'].
div_op --> ['/'].

letter_code и digit_code - это предикаты из отдельного файла tokenizer.pl 

digit_code(Code):-
    Code >= 48, /* 48 = '0' 57 = '9' */
    Code =< 57.  

letter_code(Code):-
    Code >= 97, /* 97 = 'a' 122 = 'z' */
    Code =< 122.

Когда я запускаю программу, я обычно получаю ошибку существования: letter_code / 3, то же самое с цифровым кодом, в котором он жалуется, что нет предиката с 3 аргументами. Я попытался изменить предикат, чтобы вместо него было три аргумента, но вместо этого я получил ошибку инстанцирования. Вот что я сделал и к чему приводит: 

letter_code(Code, Xs, Xs):-
    Code >= 97,
    Code =< 122.


| ?- run('program1.txt','myparsetree1.txt').
! Existence error in user:letter_code/1
! procedure user:letter_code/1 does not exist
! goal:  user:letter_code(97)
//------------------------------------------------

letter_code(Code, Xs, Xs):-
    Code >= 97,
    Code =< 122.

letter_code(Code):-
    Code >= 97,
    Code =< 122.


| ?- run('program1.txt','myparsetree1.txt').
! Instantiation error in argument 1 of (>=)/2
! goal:  _293>=97

Кто-нибудь знает, как решить эту проблему? Надеюсь, я прояснил ситуацию лучше, чем когда я впервые задал этот вопрос.

Ответы [ 2 ]

0 голосов
/ 31 января 2019

В DCG вы встраиваете код Prolog, заключив его в скобки: 

parse(I) --> assign(I).
assign(assign(I,'=', Expr,';')) -->
        {letter_code(I)}, '=', expr(Expr), ';'.
...

То есть.

0 голосов
/ 25 января 2019

В теле DCG letter_code(C) будет расширен до вызова letter_code/3. Ваша реализация с тремя аргументами ничего не удаляет из списка, поэтому я думаю, что это вряд ли даст желаемый эффект, вы, вероятно, хотите что-то вроде этого: 

letter_code(Code) --> 
    [Code], 
    {
        Code >= 97,
        Code =< 122
    }.

Правила DCG расширяются до предикатов с двумя дополнительными аргументами; например, listing(letter_code//1) показывает это как проанализированное значение: 

?- listing(letter_code//1).
letter_code(A, [A|C], B) :-
    A>=97,
    A=<122,
    B=C.

true.

Когда вы переопределите letter_code/3 с помощью letter_code(Code, Xs, Xs) :- ..., вы должны были сделать что-то, что скомпилировалось бы, но не получилось во время выполнения. Так что ваши проблемы с невозможностью найти предикаты, которые вы четко определили, лежат где-то еще.

...