В зависимости от ограничений, накладываемых на вид правил, формальные
грамматики и порождаемые ими языки делятся на четыре типа: общего вида,
контекстно - зависимые, контекстно-свободные, автоматные. На практике чаще
всего используются контекстно - свободные и автоматные языки и грамматики.
Графическим изображением вывода цепочки с помощью правил грамматики является дерево вывода или синтаксическое дерево. Каждой цепочке, выводимой в грамматике, может соответствовать одно или несколько деревьев вывода. Если цепочке соответствует не одно, а несколько деревьев вывода, то её называют неоднозначной, и грамматику, порождающую такую цепочку, также называют неоднозначной. Для таких грамматик процедура восстановления вывода для заданной цепочки значительно усложняется. |