Откат метод рекурсивного спуска для следующей грамматики

Question

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

Для данной грамматики:

a = b Z 
b = Z Z | Z 

(где строчные буквы обозначают производственные операции, а прописные буквы обозначают терминалы). Является ли производство «а» подходящим для строки «Z Z»?

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

defn parse-a (i:Int) -> [True|False, Int] : 
    val [r1, i1] = parse-b(i) 
    if r1 : eat("Z", i1) 
    else : [false, i] 

defn parse-b1 (i:Int) -> [True|False, Int] : 
    val [r1, i1] = eat("Z", i) 
    if r1 : eat("Z", i1) 
    else : [false, i] 

defn parse-b2 (i:Int) -> [True|False, Int] : 
    eat("Z", i) 

defn parse-b (i:Int) -> [True|False, Int] : 
    val [r1, i1] = parse-b1(i) 
    if r1 : [r1, i1] 
    else : parse-b2(i) 

Приведенный выше код не работает при попытке проанализировать производство «a» на входе «Z Z». Это связано с тем, что функция синтаксического анализа для «b» неверна. Он будет жадно потреблять оба Z на входе и преуспеть, а затем не оставлять ничего для анализа. Это то, что должна делать грамматика выражения синтаксического анализа? Псевдокод в диссертации Форда, похоже, указывает на это.

Большое спасибо.

-Patrick

Answer 1

В полиэтиленгликоль, дизъюнкции (варианты) действительно упорядочены. В диссертации Форда оператор записывается / и называется «заказанный выбор», который отличает его от | оператор дизъюнкции.

Это делает PEG принципиально отличным от CFG. В частности, в соответствии с правилами ПЭГ a -> b Z и b -> Z Z/Z, a не будет соответствовать Z Z.

Answer 2

Спасибо за ваш ответ Rici.

Я более внимательно прочитал тезис Форда, и он подтверждает то, что вы сказали. PEGs/оператор оба заказаны и жадные. Таким образом, приведенное выше правило должно потерпеть неудачу.

-Patrick