常规与上下文无关文法 [英] Regular vs Context Free Grammars

问题描述

我正在为我的计算语言测试进行学习，有一个主意是我遇到了麻烦。

I'm studying for my computing languages test, and there's one idea I'm having problems wrapping my head around.

我了解到常规语法更简单，不能包含歧义，但是不能完成编程语言所需的许多任务。我还理解无上下文语法允许歧义，但允许编程语言（例如回文集）进行某些必要的操作。

I understood that regular grammars are simpler and cannot contain ambiguity, but can't do a lot of tasks that are required for programming languages. I also understood that context-free grammars allow ambiguity, but allow for some things necessary for programming languages (like palindromes).

我遇到的麻烦是通过了解常规语法非终结符可以映射到终结符来理解上述所有方法或非终结符后跟一个终结符，或者上下文无关的非终结符映射到终结点和非终结点的任何组合。

What I'm having trouble with is understanding how I can derive all of the above by knowing that regular grammar nonterminals can map to a terminal or a nonterminal followed by a terminal or that a context-free nonterminal maps to any combination of terminals and nonterminals.

有人可以帮我把所有这些放在一起吗？

Can someone help me put all of this together?

推荐答案

规则语法是右线性的或左线性的，而上下文无关的语法基本上是最终和非最终的任何组合。因此，您可以看到常规语法是无上下文语法的子集。

Regular grammar is either right or left linear, whereas context free grammar is basically any combination of terminals and non-terminals. Hence you can see that regular grammar is a subset of context-free grammar.

例如，对于回文式，形式为

So for a palindrome for instance, is of the form,

S->ABA
A->something
B->something

您可以清楚地看到回文式不能以规则语法表示，因为回文式必须是左右线性的，因此不能有非终结符

You can clearly see that palindromes cannot be expressed in regular grammar since it needs to be either right or left linear and as such cannot have a non-terminal on both side.

由于正则语法是无歧义的，因此对于给定的非终结符，只有一个生产规则，而在这种情况下，可以有多个上下文无关的语法。

Since regular grammars are non-ambiguous, there is only one production rule for a given non-terminal, whereas there can be more than one in the case of a context-free grammar.

这篇关于常规与上下文无关文法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！