适合读者软考中级备考同学阅读时间3分钟内容0-3型文法的定义、产生式形式、对应自动机、对比表、例题1. 为什么需要文法分类形式语言理论中乔姆斯基Chomsky根据产生式的限制条件将文法分为四个层次0型、1型、2型、3型。不同类型的文法描述不同复杂程度的语言对应不同的自动机识别能力。软考中常考查各类文法的定义、产生式形式及其对应的自动机。2. 乔姆斯基文法体系所有文法用四元组G(VT,VN,P,S)G (V_T, V_N, P, S)G(VT​,VN​,P,S)表示其中VTV_TVT​为终结符集VNV_NVN​为非终结符集PPP为产生式集SSS为开始符号。不同类型文法的区别在于对产生式α→β\alpha \rightarrow \betaα→β的形式限制不同。2.1 0型文法短语结构文法PSG产生式形式α→β\alpha \rightarrow \betaα→β其中α\alphaα至少包含一个非终结符α,β∈(VT∪VN)∗\alpha, \beta \in (V_T \cup V_N)^*α,β∈(VT​∪VN​)∗无其他限制。特点最强大的文法可以生成任何可枚举语言。对应自动机图灵机Turing Machine。软考提示0型文法理论意义大于实用几乎不直接考查。2.2 1型文法上下文有关文法CSG产生式形式αAβ→αγβ\alpha A \beta \rightarrow \alpha \gamma \betaαAβ→αγβ其中A∈VNA \in V_NA∈VN​α,β,γ∈(VT∪VN)∗\alpha, \beta, \gamma \in (V_T \cup V_N)^*α,β,γ∈(VT​∪VN​)∗γ≠ε\gamma \neq \varepsilonγε非空。即AAA必须在特定上下文α\alphaα和β\betaβ中才能替换为γ\gammaγ。特点产生式左部长度 ≤ 右部长度非收缩。对应自动机线性有界自动机Linear Bounded Automaton。软考考点知道“上下文有关”意味着替换受周围符号限制通常不要求深入。2.3 2型文法上下文无关文法CFG产生式形式A→γA \rightarrow \gammaA→γ其中A∈VNA \in V_NA∈VN​单个非终结符γ∈(VT∪VN)∗\gamma \in (V_T \cup V_N)^*γ∈(VT​∪VN​)∗可为空串ε\varepsilonε。特点左部只有一个非终结符与上下文无关。这是程序设计语言语法描述的核心工具。对应自动机下推自动机Pushdown Automaton, PDA。软考重点大部分语法分析如算术表达式、语句结构用上下文无关文法描述。2.4 3型文法正则文法RG产生式形式右线性A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a其中A,B∈VNA, B \in V_NA,B∈VN​a∈VTa \in V_Ta∈VT​也可有ε\varepsilonε产生式。特点产生式右部最多一个非终结符且必须在最右端右线性左线性形式为A→BaA \rightarrow BaA→Ba或A→aA \rightarrow aA→a。两种形式等价。对应自动机有限自动机Finite Automaton, FA。软考重点正则文法与正则表达式、有限自动机等价常用于词法分析。3. 四种文法的对比表类型名称产生式形式对应自动机能力典型应用0型短语结构文法α→β\alpha \rightarrow \betaα→β无限制图灵机最强理论计算机1型上下文有关文法αAβ→αγβ\alpha A \beta \rightarrow \alpha \gamma \betaαAβ→αγβγ≠ε\gamma \neq \varepsilonγε线性有界自动机强自然语言处理2型上下文无关文法A→γA \rightarrow \gammaA→γ下推自动机中等程序设计语言语法3型正则文法A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a有限自动机最弱词法规则、模式匹配包含关系3型⊂\subset⊂2型⊂\subset⊂1型⊂\subset⊂0型越往上描述能力越强。4. 软考常见考点判断文法类型给定一组产生式判断属于0/1/2/3型。若产生式全部形如A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a→ 3型正则。若产生式全部左部为单个非终结符但右部有多个非终结符嵌套如E→ETE \rightarrow ETE→ET → 2型上下文无关。若产生式左部包含多个符号如aA→BcaA \rightarrow BcaA→Bc → 1型或0型通常考0型/1型区别。对应自动机知道正则文法 ↔ 有限自动机上下文无关文法 ↔ 下推自动机。实际意义词法分析用3型正则表达式语法分析用2型上下文无关文法。5. 经典例题题目1给定文法GGG的产生式如下S → aB | bA A → aS | bAA | a B → bS | aBB | b该文法属于乔姆斯基体系中的哪一型解析所有产生式左部都是单个非终结符S,A,BS, A, BS,A,B右部由终结符和非终结符组成没有上下文限制。符合2型上下文无关文法的定义。答案2型上下文无关文法题目2下列文法中属于正则文法的是 。A.S→aSb ∣ εS \rightarrow aSb \,|\, \varepsilonS→aSb∣εB.S→Aa,A→Bb,B→cS \rightarrow Aa, A \rightarrow Bb, B \rightarrow cS→Aa,A→Bb,B→cC.S→aA,A→Sb,S→εS \rightarrow aA, A \rightarrow Sb, S \rightarrow \varepsilonS→aA,A→Sb,S→εD.S→aA,A→bS \rightarrow aA, A \rightarrow bS→aA,A→b解析A 产生anbna^n b^nanbn不是正则文法需记忆计数 → 2型。B 产生式有S→AaS \rightarrow AaS→Aa左线性但A→BbA \rightarrow BbA→Bb也是左线性整体可转为右线性吗不是标准右线性但左线性等价于正则可接受。需要判断若所有产生式形如A→aA \rightarrow aA→a或A→aBA \rightarrow aBA→aB或A→BaA \rightarrow BaA→Ba左线性仍属3型。但B中S→AaS \rightarrow AaS→Aa左线性A→BbA \rightarrow BbA→Bb左线性B→cB \rightarrow cB→c终结是左线性正则文法。C 有A→SbA \rightarrow SbA→Sb左线性但S→aAS \rightarrow aAS→aA右线性混合形式仍然等价正则不过通常要求统一方向但理论上正则文法允许左线性和右线性混合严格说混合可能产生非正则语言软考中一般要求统一。C有S→εS \rightarrow \varepsilonS→ε也是允许的。但C中A→SbA \rightarrow SbA→Sb和S→aAS \rightarrow aAS→aA导致S⇒aA⇒aSbS \Rightarrow aA \Rightarrow aSbS⇒aA⇒aSb产生类似anSbna^n S b^nanSbn不是正则。D 所有产生式S→aAS \rightarrow aAS→aA右线性A→bA \rightarrow bA→b右线性符合3型。答案D题目3与上下文无关文法对应的自动机是 。A. 有限自动机B. 下推自动机C. 图灵机D. 线性有界自动机答案B6. 记忆口诀0型无限制图灵机最强1型上下文线性有界忙2型无关文下推自动掌3型正则规有限自动行。7. 给备考同学的一句话软考中文法的分类主要考查2型和3型看到产生式只有A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a形式 → 3型正则。看到产生式左部是单个非终结符但右部有像A→BCA \rightarrow BCA→BC或A→aBcA \rightarrow aBcA→aBc等嵌套形式 → 2型上下文无关。如果产生式左部有多个符号如aA→BbaA \rightarrow BbaA→Bb通常属于1型或0型软考一般不会考这么深。记住对应的自动机正则→有限上下文无关→下推考试中常以匹配题形式出现。本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅#软考中级 #软件设计师 #文法分类 #乔姆斯基体系 #上下文无关文法 #正则文法