Хомский предложил классификацию формальных грамматик по типу выражения правил и предложил выделить 4 основных типа, называемые в целом Иерархией Хомского:

|--------------------------------|
|                                           |
|Гр. 0                                    |
|                                           |
|--------------------------|      |
|Гр. 1                           |     |
|                                  |     |
|     |--------------------|     |
|     |Гр. 2                    |     |
|     |                           |     |
|     |  |--------------|    |     |
|     |  |Гр. 3            |   |     |
|     |  |                   |   |     |
|     |  |--------------|    |     |
|     |                           |     |
|     |--------------------|     |
|                                  |     |
|--------------------------|     |
|                                          |
|--------------------------------|

Грамматика типа 0 - генеративная, самая сложная, никаких ограничений на вид ее правил не накладывается. Грамматика типа 0, порождающая (generative grammar), - в классической записи это четверка G=(N,∑, P, S), где N, ∑ - алфавит (N - нетерминальные символы, ∑ - терминальные символы метаязыка); S - начальный символ нетерминального множества, Р - правила репродукции (rewriting rules).

Для распознавания языков, порождаемых этими грамматиками, используются машины Тьюринга - мощные, абстрактные, и следовательно неприменимые на практике математические модели, которые используются в теории информатики.

Грамматика типа 1 - называют контекстно-зависимыми грамматиками, и в них возможность замены цепочки символов может определяться контекстом. Используются для генерации элементов естественных языков и подъязыков.

Грамматика типа 2 - контекстно-свободные, причем в левой части нетерминала могут быть всем, чем угодно. Они распознаются в информатике так называемыми автоматами с магазинной памятью (стековые автоматы). Используются для генерации элементов языков программирования (выражений, команд).

Грамматика типа 3 - называют регулярными, самые простые и ограниченные грамматики, распознаются конечными автоматами. Используется для простых элементов языков (числа, константы, переменные).

Рисунок показывает «вхождение» одного типа грамматики в другой.

Язык называется контекстным языком, если он порождается некоторой контекстной грамматикой. Контекстно-свободные языки также называют алгебраическими языками, ими занимается математическая лингвистика (ныне раздел компьютерной лингвистики. В компьютерной лингвистике выделяют раздел - лингвистические основы информатики, который занимается проблематикой формальных языков и грамматик).

Исходная иерархия Хомского была впоследствии развита многими исследователями формального синтаксиса.

Порождение и распознавание

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

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

Задача вывода

Например, пусть дана формальная грамматика:
Б={(<Пр>, <П>, <с>, <ис>, <М>, <ГФ>), (кот, пес, он, идет, лежит), P, S = <Пр>}
Р={<Пр>→<П> <с>                           Пр - предложение
                 <П>→<ис>                                     П - подлежащее
       <П>→<М>                                    с = сказуемое
                 <ис>→кот                                    ис – имя существительное
                 <ис>→пес                                    М - местоимение
                 <М>→он                                      ГФ – глагольная форма
                 <с>→<ГФ>
       <ГФ>→идет
      <ГФ>→лежит
это можно представить или в БНФ-записи:
<Пр>: : = <П><с>
<П> : : = <ис>/<М>
<ис> : : = кот/пес
<М> : : = он
<с> : : = <ГФ>
<ГФ> : : = идет/лежит
Формальную грамматику можно представить в виде ориентированного графа для наглядности, причем, если в правую часть правил входит несколько символов, то их объединяют знаком +, для изображения правил с одинаковыми левыми частями используют узел, отмеченный знаком «или» (v).

                  <Пр>
                      ↑
                      +
                      
<П>                                        <с> 
   ↑                                              ↑
                                      
  V                                           <ГФ> 
                                
<ис>           <М>                           V
   ↑                  ↑
  кот               пес                      ↑                      ↑
                                              идет               лежит
     
Любое представление формальной грамматики, получающееся на базе правил, называется сентенциальными формами.
Наша грамматика порождает 6 правильных предложений или сентенциальных форм:
Кот идет
Кот лежит
Пес идет
Пес лежит
Он идет
Он лежит

Причем, фразу «Кот лежит» можно вывести двумя способами:
1. <Пр>  <П> <с> <ис><с> кот<с> кот<ГФ> кот лежит
2. <Пр>  <П> <с> <П><ГФ> <П>лежит <ис>лежит кот лежит

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

Дерево вывода.

Выводам контекстно-свободной грамматики соответствуют деревья разбора (derivation tree, parse tree) – это некоторые упорядоченные деревья, вершины которых помечены символами алфавита или нетерминального, или терминального множества, корень дерева – начальный символ. Каждому символу, на который заменяется начальный символ на первом шаге вывода, ставится в соответствие вершина дерева, и к ней приводится дуга из корня. Полученные таким образом потомки корня упорядочены.

Например:                            
                                      <Пр> 
                              <П>                  <с>
                                 |                        |
                              <ис>                <ГФ>
                                 |                        | 
                               кот                  лежит

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

Задача разбора

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

Например: В грамматике строка «кот лежит» прямо приводима к строке <ис>лежит……  и т.п. и в конце концов она приводима к  <Пр>.

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

По существу, термины «синтаксический анализ», «задача разбора» и «задача распознавания входной строки» это синонимы, а алгоритмы, решающие такие задачи, называются анализатором или распознавателем.