Это определенно сложная задача.
Гораздо проще создать грамматику LR для этого языка, хотя она все еще остается сложной задачей. Для начала необходимо удалить неоднозначность, которая из
<type> ::= <base_type> <optional_array_size>
<base_type> ::= <function_type>
<function_type> ::= "(" <params> ")" "->" <type>
Неоднозначность, как я уверен, вы знаете, возникает из-за незнания, является ли [42] в ()->Integer[42] частью вершины -уровень <type> или вложенный <function_type>. Чтобы устранить неоднозначность, нам нужно четко указать, какая конструкция может принимать размер массива. (Здесь я добавил желаемое произведение, которое позволяет заключить в скобки <type>):
<type> ::= <atomic_type> <optional_array_size>
| <function_type>
<opt_array_size> ::= ""
| <array_size>
<atomic_type> ::= <integer_type>
| <real_type>
| "(" <type> ")"
<function_type> ::= "(" <opt_params> ")" "->" <type>
<opt_params> ::= ""
| <params>
<params> ::= <type>
| <params> "," <type>
К сожалению, эта грамматика - LR (2), а не LR (1). Эта проблема возникает с
( Integer ) [ 42 ]
( Integer ) -> Integer
^
|
+----------------- Lookahead
. На начальном этапе анализатор по-прежнему не знает, просматривает ли он (избыточно) тип в скобках или список параметров в типе функции. Он не будет знать об этом, пока не увидит следующий символ (который может быть концом ввода, в дополнение к двум опциям выше). В обоих случаях необходимо уменьшить Integer до <atomic_type>, а затем до <type>. Но тогда, в первом случае он может просто сдвинуть закрывающую скобку, а во втором случае он должен продолжать сокращаться, сначала до <params>, а затем до <opt_params>. Это конфликт сдвига-уменьшения. Конечно, это можно легко решить, заглянув в будущее еще одним токеном, но необходимость увидеть два токена в будущем - вот что делает грамматику LR (2).
К счастью, грамматики LR (k) всегда можно свести к грамматике LR (1). (Между прочим, это не относится к грамматике LL (k).) Это просто немного запутанно, потому что необходимо ввести немного избыточности. Мы делаем это, избегая необходимости уменьшать <type> до тех пор, пока не узнаем, что у нас есть список параметров, что означает, что нам нужно принять "(" <type> ")" без фиксации одного или другого анализа. Это приводит к следующему, когда к <function_type> было добавлено явно избыточное правило, а <opt_params> было изменено для принятия либо 0, либо хотя бы двух параметров:
<type> ::= <atomic_type> <optional_array_size>
| <function_type>
<atomic_type> ::= <integer_type>
| <real_type>
| "(" <type> ")"
<function_type> ::= "(" <opt_params> ")" "->" <type>
| "(" <type> ")" "->" <type>
<opt_params> ::= ""
| <params2>
<params2> ::= <type> "," <type>
| <params2> "," <type>
Теперь я лично остановлюсь на этом. Существует множество генераторов синтаксического анализатора LR, и приведенная выше грамматика - LALR (1), и она все еще достаточно проста для чтения. Но возможно преобразовать его в грамматику LL (1), с небольшим количеством работы. (Я использовал инструмент преобразования грамматики, чтобы выполнить некоторые из этих преобразований.)
Удалять левую рекурсию, а затем левосторонний разложить грамматику просто:
# Not LL(1)
<type> ::= <atomic_type> <opt_size>
| <function_type>
<opt_size> ::= ""
| "[" integer "]"
<atomic_type> ::= <integer_type>
| <real_type>
| "(" <type> ")"
<function_type> ::= "(" <fop>
<fop> ::= <opt_params> ")" to <type>
| <type> ")" to <type>
<opt_params> ::= ""
| <params2>
<params2> ::= <type> "," <type> <params_tail>
<params_tail> ::= "," <type> <params_tail>
| ""
Но это не так достаточно, потому что <function_type> и <atomic_type> могут начинаться с "(" <type>. И есть аналогичная проблема между продукцией для списка параметров. Чтобы избавиться от этих проблем, нам нужен еще один метод: развернуть нетерминалы на месте, чтобы перевести конфликты в один и тот же нетерминал, чтобы мы могли их оставить левыми. Как и в этом примере, это часто происходит за счет некоторого дублирования.
Расширяя <atomic_type>, <function_type> и <opt_params>, мы получаем:
<type> ::= <integer_type> <opt_size>
| <real_type> <opt_size>
| "(" <type> ")" <opt_size>
| "(" ")" "->" <type>
| "(" <type> ")" "->" <type>
| "(" <type> "," <type> <params2> ")" "->" <type>
<opt_size> ::= ""
| "[" INTEGER_LITERAL "]"
<params2> ::= ""
| "," <type> <params2>
И затем мы можно с левым коэффициентом произвести
<type> ::= <integer_type> <opt_size>
| <real_type> <opt_size>
| "(" <fop>
<fop> ::= <type> <ftype>
| ")" "->" <type>
<ftype> ::= ") <fcp>
| "," <type> <params2> ")" "->" <type>
<fcp> ::= <opt_size>
| "->" <type>
<opt_size> ::= ""
| "[" INTEGER_LITERAL "]"
<params2> ::= ""
| "," <type> <params2>
, что составляет LL (1). Я оставлю это как упражнение, чтобы присоединить все соответствующие действия к этим постановкам.