Комбинировщик Parser - заказный выбор и левая рекурсия

Question

Каково значение ordered choice? Означает ли это, что вы сначала ставите самый длинный шаблон?

Допустим, вы имели это выражение»

val expr = "eat" ~ "more" ~ "beans" | 
      "eat" ~ "more" ~ "beans" ~ "and" ~ "fruit" 

Поскольку комбинаторы синтаксического анализа используют Ordered Choice, строка eat more beans and soup ... приведет к соответствие на первой линии? val expr использует Ordered Choice плохо, так как она включает в себя менее конкретное выражение первой ?

Кроме того, что left recursion?

Answer 1

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

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

Левая рекурсия происходит в том случае, если для производства формы a = b расширение b начинается с a. Рассмотрим:

def a = b ~ c 
def b = a ~ c 

расширения (соответствия) производственных a протекает следующим образом:

b ~ c 
(a ~ c) ~ c    // substituting b 
((b ~ c) ~ c) ~ c  // substituting a 
(((a ~ c) ~ c) ~ c) ~ c // substituting b 

Это фактически бесконечное, незавершенная рекурсии.