Метод грамматического разбора сверху-вниз. LL (1) — грамматики
Берем каждый нетерминал, если для него есть продукция, учитывающая нетерминал, стоящий левее, и преобразуем грамматику: Определяем на множестве нетерминалов какой-либо порядок (А1, А2, …, Аn). Для такого случая существует алгоритм, исключающий левую рекурсию: Исключаем все случаи непосредственной левой рекурсии (правило1). Грамматика относится к классу LL (1) если FIRST (б)? FIRST (в… Читать ещё >
Метод грамматического разбора сверху-вниз. LL (1) — грамматики (реферат, курсовая, диплом, контрольная)
Суть: начинаем разбор со стартового нетерминала и, применяя продукции, заменяем нетерминал ее левой части на последовательность символов ее правой части. Цель: получить в обрамлении листьев этого дерева исходную последовательность.
Как сделать выбор среди двух продукций: A > б | в?
x? FIRST (б)? б ?* x г е? FIRST (б)? б ? е.
Грамматика относится к классу LL (1) если FIRST (б)? FIRST (в) =? ,.
а если б ?* е то должно выполняться FIRST (в)? FOLLOW (A) =? .
Для правой части продукции определить множество FIRST, как множество нетерминалов, с которого может начинаться выводимая этим правилом последовательность. А для каждого нетерминала определить множество FOLLOW, т. е. множество следующих нетерминалов, которые могут встретиться непосредственно за этим нетерминалом.
Исключение левой рекурсии
Для такого случая существует алгоритм, исключающий левую рекурсию:
- 1) определяем на множестве нетерминалов какой-либо порядок (А1, А2, …, Аn)
- 2) берем каждый нетерминал, если для него есть продукция, учитывающая нетерминал, стоящий левее, и преобразуем грамматику:
for i:=1 to n do.
for j:=1 to i-1 do.
if Ai > Ajг then Ai>д1г.
¦ д2г.
¦ дkг, где.
Aj > д1¦ д2¦ …¦ дk.
3) исключаем все случаи непосредственной левой рекурсии (правило1).