грамматик && LL Парсеры

Question

Так у меня есть домашнее задание, и я потратил более 2 часов, пытаясь выяснить, почему эта грамматика не будет работать с LL парсер:

<A> → a <B> 
<A> → a b <C> 
<B> → b d <D> 
<C> → d <E> 
<D> → m n 
<E> → x y 

Может кто-то пожалуйста мне точку в правильном направление? Я знаю, что один из способов, которым LL может сработать, заключается в том, что он сталкивается с бесконечным циклом, который я не верю, что он здесь.

Благодаря

Answer 1

Я полагаю, что LL Parser вы имеете в виду LL (1) парсер (в LL Parser с опережающим просмотром 1)

Для грамматики быть синтаксической-состояние с помощью LL (1) синтаксических анализаторов , он должен быть LL (1). Есть несколько вещей, которые должна соблюдать грамматика, чтобы быть LL (1), если она разбивает одну из них, она называется конфликтом LL (1).

• ПЕРВЫЙ/ПЕРВЫЙ Конфликт:

  Для каждого не-терминала, каждое производство должно иметь непересекающийся первый набор. (Первый набор представляет собой набор из всех терминалов, которые могут начинаться предложения, полученные от субъекта.)

  ЭГ: В вашем примере выше, не-терминал имеет две постановки:

  <A> -> a <B> 
  <A> -> a b <C> 
  

  Первые наборы каждая из производств представлена ​​следующим образом:

  FIRST(a <B>) = {a} 
  FIRST(a b <C>) = {a} 
  

  Вы можете совершенно ясно видеть, что эти два набора пересекаются. Это проблема, потому что в парсере LL, если точка достигнута, где A находится в стеке, а следующий символ, который должен быть прочитан, равен 'a', тогда синтаксический анализатор не знает, следует ли выбрать <A> -> a <B> или <A> -> a b <C>.

• ПЕРВЫЙ/ПОСЛЕДУЮЩИЕ Конфликт:

  Это происходит, когда, для конкретного нетерминальный A; FOLLOW(A) и FIRST(A) пересекаются и A - NULLABLE. Этот конкретный конфликт не возникает в вашем примере.

Для получения более подробной информации о FIRST, FOLLOW и NULLABLE, я бы

Для получения более подробной информации об этих конфликтах, а также некоторые примеры см the Wikipedia page on LL(1) Conflicts.