Как я могу избежать левой рекурсии в вершине дерева без возврата?

У меня возникли проблемы с тем, чтобы избежать левой рекурсии в этом простом синтаксическом анализаторе выражений, над которым я работаю. По сути, я хочу разобрать уравнение «f x y» на два выражения «f x» и «(f x) y» (с неявными скобками). Как я могу сделать это, избегая левой рекурсии и возврата? Должен ли быть промежуточный шаг?

#!/usr/bin/env ruby
require 'rubygems'
require 'treetop'
Treetop.load_from_string DATA.read

parser = ExpressionParser.new

p parser.parse('f x y').value

__END__
grammar Expression
   rule equation
      expression (w+ expression)*
   end
   rule expression
      expression w+ atom
   end
   rule atom
      var / '(' w* expression w* ')'
   end
   rule var
      [a-z]
   end
   rule w
      [\s\n\t\r]
   end
end

ruby parsing left-recursion peg treetop
person Josh Voigts    schedule 20.08.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы не предоставили достаточно информации о желаемом результате. В частности, ожидаете ли вы, что "f(a b) y" будет анализироваться как "(f(a(b))) y"? Я предполагаю, что вы делаете... что означает, что функция, за которой не следует открывающая скобка, имеет арность один.

Итак, вы хотите сказать:

rule equation
  expression w* var / expression w* parenthesised_list
end
rule parenthesised_list
  '(' w* ( expression w* )+ ')'
end

Если, с другой стороны, у вас есть внешнее (по отношению к грамматике) знание арности f, и вы хотите повторять «выражение» ровно столько раз — как это происходит, например, при разборе TeX — тогда вам нужно будет использовать семантический предикат &{|с| ...} внутри повторяющегося списка выражений). Имейте в виду, что аргумент, передаваемый блоку sempred, является не SyntaxNode (который еще не может быть создан, поскольку это подправило последовательности еще не выполнено), а совокупным массивом узлов в последовательности. Правдивость возвращаемого значения блока определяет результат синтаксического анализа и может остановить итерацию.

Еще один инструмент, который вы можете использовать, — это просмотр вперед (!stuff_I_dont_expect_to_follow или &stuff_that_must_follow).

Вы также можете задать такие вопросы в http://groups.google.com/group/treetop-dev< /а>

person Clifford Heath    schedule 31.08.2012
comment
Если я правильно понимаю OP, автор хочет синтаксис, подобный Haskell, поэтому открывающие круглые скобки используются не для списков аргументов, а для группировки выражений. - person Niklas B.; 31.08.2012
comment
Это именно тот синтаксис, который я искал. Treetop, однако, не отступает... поэтому нет возможности вернуться к повторному анализу f x в (f x). Может быть, я неправильно понимаю, как такие языки, как Haskell или SASL, анализируют такие вещи? - person Josh Voigts; 31.08.2012