2022年軟件設(shè)計(jì)師考試真題回顧：文法

【考法分析】

本知識(shí)點(diǎn)主要以選擇題形式考察文法的主要內(nèi)容。

【要點(diǎn)分析】

文法和語(yǔ)言的形式描述

定義：描述語(yǔ)言語(yǔ)法結(jié)構(gòu)的規(guī)則

分類：?jiǎn)棠匪够–homsky）把文法分成 4 種類型，即 0 型、1 型、2 型和 3型。這 4 類文法之間的差別在于對(duì)產(chǎn)生式要施加不同的限制。若文法 G=（VV，P， S）的每個(gè)產(chǎn)生式α→β，均有αe（VyUV，）*，α至少含有一個(gè)非終結(jié)符，且βe（V，Ur，）"，則稱G為0型文法。對(duì)0型文法的每條產(chǎn)生式分別施加以下限制，則可得以下文法。

1型文法∶ G的任何產(chǎn)生式α→β（S→ε除外）均滿足|q|≤8（|x表示x中文法符號(hào)的個(gè)數(shù)）。

2 型文法∶ G的任何產(chǎn)生式形如A→β，其中 A∈Vw，βe（V，UV，）"。

3 型文法∶ G的任何產(chǎn)生式形如 A→a或 A→aB（或者 A→Ba），其中 A，B∈Vy，a∈V

0型文法也稱為短語(yǔ)文法，其功能相當(dāng)于圖靈機(jī)，任何0型語(yǔ)言都是遞歸可枚舉的;反之，遞歸可枚舉集也必定是一個(gè)0型語(yǔ)言。1型文法也稱為上下文有關(guān)文法，這種文法意味著對(duì)非終結(jié)符的替換必須考慮上下文，并且一般不允許替換成ε串。

【備考點(diǎn)撥】

句子和語(yǔ)言。設(shè)有文法 G=（V，， V7， P，S）

推導(dǎo)與直接推導(dǎo)∶推導(dǎo)就是從文法的開(kāi)始符號(hào) S出發(fā)，反復(fù)使用產(chǎn)生式，將產(chǎn)生式左部的非終結(jié)符替換為右部的文法符號(hào)序列（展開(kāi)產(chǎn)生式用→ 表示），直到產(chǎn)生一個(gè)終結(jié)符的序列時(shí)為止。

【相關(guān)試題】

簡(jiǎn)單算術(shù)表達(dá)式的結(jié)構(gòu)可以用下面的上下文無(wú)關(guān)文法進(jìn)行描述(E為開(kāi)始符號(hào))，( )是符合該文法的句子。

E→T|E+T

T→F|T*F

F→-F|N

N→0|1|2|3l4|5|6|7|8|9

A.2--3*4

B.2+-3*4

C.(2+3)*4

D.2*4-3

信管網(wǎng)參考答案及解析：B  m.xiexiliangjiufa.com/st/3961312318.html