Формальные языки

Левый и правый выводы


    Среди всевозможных выводов наибольший интерес представляют следующие два типа выводов.

 

Определение.  Если при построении вывода цепочки a

при каждом применении правила заменяется самый левый нетерминальный символ, то такой вывод называется левым или

левосторонним выводом a.

Если при построении вывода a, всегда заменяется самый правый нетерминальный символ промежуточной цепочки, то вывод называется правым или правосторонним

выводом a.

 

    Например, приведенный выше вывод цепочки i * i + i в грамматике Г1. 9 является левосторонним выводом. Следует отметить, что различным выводам цепочки i+i в грамматике

    Г1. 9 соответствует одно и то же синтаксическое дерево. Аналогичная ситуация имеет место и при выводе цепочки

    i * i + i.

Пред.Страница  След.Страница   Раздел   Содержание


 



Содержание раздела