Нисходящий и восходящий парсинг

Рассмотрим многие понятия формальных грамматик на простых примерах. Набор правил синтаксиса любого языка, как искусственного, так и естественного, может описывать либо процедуры получения правильных предложений (т.е. порождение языка), либо процедуру распознавания правильного предложения, т.е. процедуру распознавания принадлежности предложений этому языку. В первом случае грамматику называют порождающей, во втором – распознающей, в любом случае принцип построения такой грамматики один и тот же.

Например, пусть дана формальная грамматика:

Б={(<Пр>, <П>, <с>, <ис>, <М>, <ГФ>), (кот, пес, он, идет, лежит), P, S = <Пр>}

Р={<Пр>→<П> <с> Пр - предложение

<П>→<ис> П - подлежащее

<П>→<М> с = сказуемое

<ис>→кот ис – имя существительное

<ис>→пес М - местоимение

<М>→он ГФ – глагольная форма

<с>→<ГФ>

<ГФ>→идет

<ГФ>→лежит

БНФ:

<Пр>:: = <П><с>

<П>:: = <ис>/<М>

<ис>:: = кот/пес

<М>:: = он

<с>:: = <ГФ>

<ГФ>:: = идет/лежит

Формальную грамматику можно представить в виде ориентированного графа для наглядности, причем, если в правую часть правил входит несколько символов, то их объединяют знаком +, для изображения правил с одинаковыми левыми частями используют узел, отмеченный знаком «или» (v).

<Пр>

↑

+

<П> <с>

↑ ↑

V <ГФ>

<ис> <М>

↑ ↑

кот пес

идет лежит

Любое представление формальной грамматики, получающееся на базе правил, называется сентенциальными формами.

Наша грамматика порождает 6 правильных предложений или сентенциальных форм:

Кот идет

Кот лежит

Пес идет

Пес лежит

Он идет

Он лежит

«Кот лежит» можно вывести двумя способами:

1. <Пр> <П> <с> <ис><с> кот<с> кот<ГФ> кот лежит

2. <Пр> <П> <с> <П><ГФ> <П>лежит <ис>лежит кот лежит

По определению каждой сентенциальной форме должен соответствовать один вывод, однако на практике это редко бывает, разные выводы приводят к разным деревьям вывода, особенно для сложных фраз и конструкций языков, и вывод любой фразы можно представить так называемым синтаксическим деревом (дерево вывода или разбора).