Застрял на переводе cfg в dcg

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

<expression> --> number
<expression> --> ( <expression> )
<expression> --> <expression> + <expression>
<expression> --> <expression> - <expression>
<expression> --> <expression> * <expression>
<expression> --> <expression> / <expression>

До сих пор я писал это на swi-prolog, который устраняет ряд ошибок, описанных ниже;

expression(N) --> number(Cs), { number_codes(N, Cs) }.
expression(N) --> "(", expression(N), ")".
expression(N) --> expression(X), "+", expression(Y), { N is X + Y }.
expression(N) --> expression(X), "-", expression(Y), { N is X - Y }.

number([D|Ds]) --> digit(D), number(Ds).
number([D])    --> digit(D).

digit(D) --> [D], { code_type(D, digit) }.

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

phrase(expression(X), "12+4").

дает X = 16, что хорошо. Также

phrase(expression(X), "(12+4)").

произведения и фраза(выражение(X), "12+4+5"). в порядке.

Но пытаясь

phrase(expression(X), "12-4").

вызывает «ОШИБКА: вне локального стека», если я не прокомментирую правило «+». И хотя я могу добавить более двух чисел, скобки не работают рекурсивно (т.е. "(1+2)+3" зависает).

Я уверен, что решение простое, но я не смог понять его из онлайн-учебников, которые я нашел.


prolog dcg context-free-grammar
person joeblog    schedule 31.03.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Все, что вы сделали, в принципе правильно. И вы правы: ответ прост.

Но.

Левая рекурсия фатальна в грамматиках с определенным предложением; симптом — это именно то поведение, которое вы видите.

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

gtrace.
spy(expression).
phrase(expression(N),"12-4").

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

  1. Мы пытаемся разобрать "12-4" как выражение.

    Наш стек вызовов содержит этот вызов expression из шага 1, который я напишу expression(1).

  2. Нам удается разобрать «12» как выражение по первому предложению для «выражения», и мы записываем точку выбора на случай, если нам понадобится вернуться позже. На самом деле нам нужно немедленно вернуться назад, потому что родительский запрос, включающий phrase, говорит, что мы хотим проанализировать всю строку, а мы этого не сделали: у нас еще есть "-4". Таким образом, мы терпим неудачу и возвращаемся к точке выбора. Мы показали, что первое предложение «выражения» не удалось, поэтому мы повторяем попытку со вторым предложением.

    Стек вызовов: expression(1).

  3. Мы пытаемся разобрать «12-4», используя второе предложение для «выражения», но немедленно терпят неудачу (начальный символ не «(»). Поэтому мы терпят неудачу и повторяем попытку с третьим предложением.

    Стек вызовов: expression(1).

  4. Третье предложение просит нас разобрать выражение в начале ввода, а затем найти «+» и другое выражение. Итак, теперь мы должны попытаться разобрать начало ввода как выражение.

    Стек вызовов: expression(4) expression(1).

  5. Мы пытаемся разобрать начало «12-4» как выражение и преуспеваем с «12», как и в шаге 1. Мы записываем точку выбора на случай, если нам понадобится вернуться позже.

    Стек вызовов: expression(4) expression(1).

  6. Теперь мы возобновим попытку, начатую на шаге 4, разобрать «12-4» как выражение против пункта 3 «выражения». Мы сделали первый бит; теперь мы должны попытаться разобрать "-4" как оставшуюся часть правой части пункта 3 "выражения", а именно "+", expression(Y). Но «-» — это не «+», поэтому мы сразу потерпим неудачу и вернемся к самой последней записанной точке выбора, записанной на шаге 5. Следующее, что нужно сделать, это попытаться найти другой способ разбора начала ввод как выражение. Мы возобновим этот поиск со вторым пунктом «выражения».

    Стек вызовов: expression(4) expression(1).

  7. И снова второй пункт не работает. Итак, мы продолжаем с третьим предложением «выражения». Это просит нас искать выражение в начале ввода (как часть выяснения того, могут ли наши текущие два вызова «выражения» быть успешными или нет). Итак, мы снова называем «выражение».

    Стек вызовов: expression(7) expression(4) expression(1).

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

Краткий ответ: левая рекурсия фатальна в DCG.

Это также фатально в парсерах с рекурсивным спуском, и решение почти такое же: не возвращаться влево.

Нелеворекурсивная версия вашей грамматики будет:

expression(N) --> term(N).
expression(N) --> term(X), "+", expression(Y), { N is X + Y }.
expression(N) --> term(X), "-", expression(Y), { N is X - Y }.
term(N) --> number(Cs), { number_codes(N, Cs) }.
term(N) --> "(", expression(N), ")".

Тем не менее, это делает "-" правильной ассоциативностью и во многих случаях требует многократного повторного анализа начального термина, поэтому общий подход к коду, предназначенному для производства, состоит в том, чтобы сделать что-то меньше похожее на BNF, с которого вы начали, и больше похожее на следующую версию EBNF. :

expression = term {("+"|"-") term}
term = number | "(" expression ")".

То, как я научился писать это (достаточно давно, и я уже не помню, кому это нужно), примерно так (сначала я нашел это уродливым, но оно растет на вас):

expression(N) --> term(X), add_op_sequence(X,N).
add_op_sequence(LHS0, Result) -->
    "+", term(Y),
    {LHS1 is LHS0 + Y},
    add_op_sequence(LHS1,Result).
add_op_sequence(LHS0, Result) -->
    "-", term(Y),
    {LHS1 is LHS0 - Y},
    add_op_sequence(LHS1,Result).
add_op_sequence(N,N) --> [].

term(N) --> number(Cs), { number_codes(N, Cs) }.
term(N) --> "(", expression(N), ")".

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

Стратегия синтаксического анализа, известная как «анализ левого угла», является способом решения этой проблемы; книги по использованию Пролога в обработке естественного языка почти всегда обсуждают его.

person C. M. Sperberg-McQueen    schedule 01.04.2015