Формальная грамматика: различия между версиями
Содержимое удалено Содержимое добавлено
перенос из старой версии w:Формальная грамматика, см. также страницу обсуждения для информации об авторских правах |
м мелкие исправления ссылок |
||
Строка 84:
по правилам вывода.
==Пример вывода==
Строка 109 ⟶ 101 :
В приведенном примере с левой стороны от стрелки <math>\Rightarrow</math> в
каждом правиле вывода стоял только один нетерминальный символ. Такие грамматики
называются [[w:контекстно-свободная грамматика|контекстно-свободными]]. Это не
единственный вид грамматик, однако наиболее распространенный в приложениях к
программированию. В отличие от порождающих грамматик, пример которой был
рассмотрен выше, распознающая грамматика задает алгоритм, позволяющий
определить, принадлежит ли данное слово языку. Например, любой [[w:регулярный язык|регулярный язык]] может быть распознан при помощи грамматики, задаваемой [[w:конечный автомат|конечным автоматом]], а любая контекстно-свободная грамматика — с
помощью [[w:автомат со стековой памятью|автомата со стековой памятью]]. Если
слово принадлежит языку, то такой автомат строит его вывод в явном виде, что
Строка 126 ⟶ 118 :
== Применение ==
* [[w:контекстно-свободная грамматика|Контекстно-свободные грамматики]] широко применяются для определения грамматической структуры в [[w:грамматический анализ|грамматическом анализе]].
* [[w:регулярные грамматики|регулярные грамматики]] (в виде [[w:регулярные выражения|регулярных выражений]]) широко применяются как шаблоны для текстового поиска, разбивки и подстановки, в т.ч. в [[w:лексический анализ|лексическом анализе]].
== См. также ==
| |||