Разбор выражения в Прологе и возврат абстрактного синтаксиса

Question

Я должен написать parse(Tkns, T), который принимает математическое выражение в форме списка токенов и находит T, и возвращает инструкцию, представляющую абстрактный синтаксис, соблюдая порядок операций и ассоциативность.

Например,

?- parse( [ num(3), plus, num(2), star, num(1) ], T ).

T = add(integer(3), multiply(integer(2), integer(1))) ;
No

Я попытался реализовать + и * следующим образом

parse([num(X)], integer(X)).
parse(Tkns, T) :-
  (  append(E1, [plus|E2], Tkns),
     parse(E1, T1),
     parse(E2, T2),
     T = add(T1,T2)
  ;  append(E1, [star|E2], Tkns),
     parse(E1, T1),
     parse(E2, T2),
     T = multiply(T1,T2)
  ).

Который находит правильный ответ, но также возвращает ответы, которые не соответствуют ассоциативности или порядку операций.

ех)

parse( [ num(3), plus, num(2), star, num(1) ], T ). 

также возвращает

mult(add(integer(3), integer(2)), integer(1))

а также

parse([num(1), plus, num(2), plus, num(3)], T)

возвращает эквивалент 1+2+3 и 1+(2+3), когда он должен возвращать только первое.

Есть ли способ, которым я могу заставить это работать?

Изменить: дополнительная информация: мне нужно только реализовать +,-,*,/, отрицание (-1, -2 и т. Д.) И все числа являются целыми числами. Намек был дан, что код будет структурирован аналогично грамматике

<expression> ::= <expression> + <term>
              |  <expression> - <term>
              |  <term>

      <term> ::= <term> * <factor>
              |  <term> / <factor>
              |  <factor>

    <factor> ::= num
              |  ( <expression> )

Только с реализованным отрицанием.

Edit2: я нашел анализатор грамматики, написанный на прологе ( http://www.cs.sunysb.edu/~warren/xsbbook/node10.html). Есть ли способ, которым я мог бы изменить его, чтобы вывести левосторонний вывод грамматики ("print" в том смысле, что интерпретатор Prolog выведет "T=[правильный ответ]")

Answer 1

Удаление левой рекурсии приведет вас к грамматике на основе DCG.

Но есть интересный альтернативный способ: реализовать синтаксический анализ снизу вверх.

Насколько это сложно в Прологе? Что ж, как показывают Перейра и Шибер в своей замечательной книге "Пролог и анализ естественного языка", это может быть действительно легко: из главы 6.5

Prolog по умолчанию предоставляет алгоритм синтаксического разбора возврата сверху вниз, слева направо для DCG.

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

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

В качестве альтернативы мы можем рассмотреть возможность реализации метода синтаксического анализа снизу вверх непосредственно в Прологе. Из различных возможностей мы рассмотрим здесь метод левого угла в одной из его адаптаций к DCG.

Для удобства программирования входная грамматика для левого угла интерпретатора DCG представлена ​​в небольшом отклонении записи DCG. Правые части правил представлены в виде списков, а не соединений литералов. Таким образом, правила являются единичными предложениями вида, например,

s ---> [np, vp].

или же

optrel ---> [].

Терминалы вводятся в виде словарных единиц формы слова (w,PT).

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

Теперь давайте попробуем написать процессор снизу вверх:

:- op(150, xfx, ---> ).

parse(Phrase) -->
    leaf(SubPhrase),
    lc(SubPhrase, Phrase).

leaf(Cat) --> [Word], {word(Word,Cat)}.
leaf(Phrase) --> {Phrase ---> []}.

lc(Phrase, Phrase) --> [].

lc(SubPhrase, SuperPhrase) -->
    {Phrase ---> [SubPhrase|Rest]},
    parse_rest(Rest),
    lc(Phrase, SuperPhrase).

parse_rest([]) --> [].
parse_rest([Phrase|Phrases]) -->
    parse(Phrase),
    parse_rest(Phrases).

% that's all! fairly easy, isn't it ?

% here start the grammar: replace with your one, don't worry about Left Recursion
e(sum(L,R)) ---> [e(L),sum,e(R)].
e(num(N)) ---> [num(N)].

word(N, num(N)) :- integer(N).
word(+, sum).

что, например, дает

phrase(parse(P), [1,+,3,+,1]).
P = e(sum(sum(num(1), num(3)), num(1))) 

обратите внимание, что левая рекурсивная грамматика используется e ::= e + e | num

Answer 2

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

Это очень полезная стратегия отладки в Прологе: посмотрите на все ответы.

Далее следует конкретный способ, как вы закодировали грамматику. На самом деле, вы сделали что-то очень умное: по сути, вы закодировали леворекурсивную грамматику - тем не менее ваша программа завершает работу со списком фиксированной длины! Это потому, что в каждой рекурсии вы указываете, что в середине должен быть хотя бы один элемент, выполняющий роль оператора. Таким образом, для каждой рекурсии должен быть хотя бы один элемент. Это хорошо. Однако эта стратегия по своей сути очень неэффективна. Для каждого применения правила необходимо учитывать все возможные разделы.

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

?- parse(S, add(add(integer(1),integer(2)),integer(3))).

Есть две причины: во-первых, что цели T = add(...,...) слишком поздно Просто поместите их в начале перед append/3 цели. Но гораздо интереснее то, что сейчас append/3 не прекращается. Вот соответствующий фрагмент ошибки (см. Ссылку для более подробной информации).

parse ([число (X)], целое число (X)):- ложно.
Разбор (Tkns, T):-
  (  T = добавить (T1,T2),
     добавить (E1, [плюс |E2], Tkns), ложь,
     анализ (E1, T1),
     разбор (E2, T2),; ложь, T = умножить (T1, T2),
     добавить (E1, [звезда | E2], Tkns),
     анализ (E1, T1),
     разбор (E2, T2),).

@DanielLyons уже дала вам "традиционное" решение, которое требует всевозможных обоснований со стороны формальных языков. Но я буду придерживаться вашей грамматики, которую вы закодировали в своей программе, которая в переводе на DCG гласит:

expr (целое число (X)) -> [число (X)].
expr(добавить (L,R)) -> expr(L), [плюс], expr(R).
expr(умножить (L,R)) -> expr(L), [звезда], expr (R).

При использовании этой грамматики с ?- phrase(expr(T),[num(1),plus,num(2),plus,num(3)]). это не прекратится. Вот соответствующий срез:

expr (целое число (X)) -> {false}, [num (X)].
expr (add (L,R)) -> expr (L), {false}, [plus], expr (R).expr (multiply (L,R)) -> {false} expr (L), [star], expr (R).

Так что это крошечная часть, которая должна быть изменена. Обратите внимание, что правило "знает", что оно хочет один символ терминала, увы, терминал появляется слишком поздно. Если бы только это произошло перед рекурсией! Но это не так.

Существует общий способ исправить это: добавить еще одну пару аргументов для кодирования длины.

Разбор (T, L):-
   фраза (expr(T, L,[]), L).

expr(целое число (X), [_|S],S) -> [num(X)].
expr(добавить (L,R), [_|S0],S) -> expr(L, S0,S1), [плюс], expr(R, S1,S).
expr(умножить (L,R), [_|S0],S) -> expr(L, S0,S1), [star], expr(R, S1,S).

Это очень общий метод, который представляет особый интерес, если у вас есть неоднозначные грамматики или если вы не знаете, является ли ваша грамматика неоднозначной. Просто позвольте Прологу думать за вас!

Answer 3

Правильный подход - использовать DCG, но ваша примерная грамматика является леворекурсивной, что не сработает. Вот что бы:

expression(T+E) --> term(T), [plus], expression(E).
expression(T-E) --> term(T), [minus], expression(E).
expression(T)   --> term(T).

term(F*T) --> factor(F), [star], term(T).
term(F/T) --> factor(F), [div], term(T).
term(F)   --> factor(F).

factor(N) --> num(N).
factor(E) --> ['('], expression(E), [')'].

num(N) --> [num(N)], { number(N) }.

Отношение между этим и вашей примерной грамматикой должно быть очевидным, равно как и преобразование из левой рекурсивной в правую рекурсивную. Я не могу вспомнить подробности из моего класса автоматов о самых левых деривациях, но я думаю, что это вступает в действие только тогда, когда грамматика неоднозначна, и я не думаю, что это так. Надеемся, что подлинный компьютерщик придет и прояснит этот момент.

Я не вижу смысла в создании AST, кроме того, что использовал бы Prolog. Код в круглых скобках с левой стороны производства является строительным кодом AST (например, T+E во-первых expression//1 правило). Измените код соответствующим образом, если это нежелательно.

Отсюда, представляя ваш parse/2 API довольно тривиально:

parse(L, T) :- phrase(expression(T), L).

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

?- parse([num(4), star, num(8), div, '(', num(3), plus, num(1), ')'], T).
T = 4* (8/ (3+1)) ;
false.

Вы можете показать более вывод AST-у, если вам нравится использовать write_canonical/2:

?- parse([num(4), star, num(8), div, '(', num(3), plus, num(1), ')'], T),
   write_canonical(T).
*(4,/(8,+(3,1)))
T = 4* (8/ (3+1)) a

Часть *(4,/(8,+(3,1))) является результатом write_canonical/1, И вы можете оценить это непосредственно с is/2:

?- parse([num(4), star, num(8), div, '(', num(3), plus, num(1), ')'], T),
   Result is T.
T = 4* (8/ (3+1)),
Result = 8 ;
false.