Важной деталью здесь является то, что грамматики не принимают строки; они генерируют строки. Грамматики - это описания языков, которые предоставляют средства для генерации всех возможных строк, содержащихся в языке. Чтобы определить, содержится ли конкретная строка в языке, вы должны использовать распознаватель , своего рода автомат, который обрабатывает данную строку и говорит «да» или «нет».
A контекстно-свободная грамматика (CFG) - это грамматика, в которой (как вы заметили) каждое произведение имеет форму A & rarr; w, где A - нетерминал, а w - строка терминалов и нетерминалов. Неформально, CFG - это грамматика, где любой нетерминал может быть распространен на любое из его произведений в любой точке. Язык грамматики - это набор строк терминалов, которые могут быть получены из начального символа.
A context- чувствительный грамматика (CSG) - это грамматика, в которой каждое произведение имеет форму wAx & rarr; wyx, где w и x - строки терминалов и нетерминалов, а y - также строка терминалов. Другими словами, в постановках содержатся правила, гласящие: «если вы видите A в данном контексте , вы можете заменить A на строку y». К сожалению, эти грамматики называются «контекстно-зависимыми грамматиками», потому что это означает, что «контекстно-свободные» и «контекстно-зависимые» не являются противоположностями, и это означает, что существуют определенные классы грамматик, которые, возможно, занимают много контекстуального информация учитывается, но формально не считается контекстно-зависимой.
Чтобы определить, содержится ли строка в CFG или CSG, существует много подходов. Во-первых, вы можете создать распознаватель для данной грамматики. Для CFG push-автомат (PDA) представляет собой тип автомата, который принимает точно контекстно-свободные языки, и существует простая конструкция для превращения любого CFG в PDA. Для контекстно-зависимых грамматик используемый вами автомат называется линейный ограниченный автомат (LBA).
Однако указанные выше подходы при наивном подходе не очень эффективны. Чтобы определить, содержится ли строка в языке CFG, существуют гораздо более эффективные алгоритмы. Например, многие грамматики могут иметь встроенные парсеры LL (k) или LR (k) , что позволяет вам (за линейное время) решить, содержится ли строка в грамматика. Все грамматики могут быть проанализированы с помощью синтаксического анализатора Earley , который в O (n 3 ) может определить, содержится ли строка длины n в грамматике (интересно, она может анализировать любой однозначный код) CFG в O (n 2 ), и с предвидением может проанализировать любую грамматику LR (k) за O (n) время!). Если бы вас просто интересовал вопрос «содержится ли строка x в языке, сгенерированном грамматикой G?», То один из этих подходов был бы превосходным. Если вы хотите узнать, как была сгенерирована строка x (найдя дерево разбора ), вы можете адаптировать эти подходы, чтобы также предоставить эту информацию. Тем не менее, синтаксический анализ CSG, как правило, PSPACE-завершен, поэтому для них не существует известных алгоритмов синтаксического анализа, которые выполняются за наихудшее полиномиальное время. Однако есть некоторые алгоритмы, которые на практике имеют тенденцию работать быстро. Авторы Методы синтаксического анализа: практическое руководство (см. Ниже) соединили фантастическую страницу, содержащую все виды алгоритмов синтаксического анализа , включая один, который анализирует контекстно-зависимые языки.
Если вам интересно узнать больше о разборе, рассмотрите отличную книгу Груна и Джейкобса " Методы синтаксического анализа: практическое руководство, второе издание ", в которой рассматриваются всевозможные алгоритмы синтаксического анализа для определение, содержится ли строка в грамматике и, если да, то как она генерируется алгоритмом синтаксического анализа.
Надеюсь, это поможет!