Ограничения правил контекстно-свободных грамматик. Восстановление контекстно-свободных грамматик, использование свойства факторизуемости правых частей правил вывода. Специфика процесса устранения нетерминалов, допускающих неукорачивающую факторизацию.
Аннотация к работе
В работе показывается, что на правила контекстно-свободных грамматик можно наложить существенные ограничения, которые позволяют развивать конструктивные методы грамматического вывода. · запись a ?G b означает, что цепочка b выводима из цепочки a в грамматике G, т.е. b может быть получена из a применением конечного числа правил; С точки зрения грамматического вывода класс КС-грамматик можно изначально ограничить только такими грамматиками, в которых: · отсутствуют e-правила - правила с пустой правой частью e - за исключением быть может правила S ® e; A допускает неукорачивающую левую факторизацию в КС-грамматике G, то G можно трансформировать в грамматику GA, применив следующее ЛНФ-преобразование: - шаг 1 - исключить из G все А-правила; A? не допускает неукорачивающую левую факторизацию; но в грамматике GA может появиться [другой] нетерминал, допускающий неукорачивающую левую факторизацию.