2022年軟件設計師考試真題回顧：文法

【考法分析】

本知識點主要以選擇題形式考察文法的主要內容。

【要點分析】

文法和語言的形式描述

定義：描述語言語法結構的規(guī)則

分類：喬姆斯基（Chomsky）把文法分成 4 種類型，即 0 型、1 型、2 型和 3型。這 4 類文法之間的差別在于對產生式要施加不同的限制。若文法 G=（VV，P， S）的每個產生式α→β，均有αe（VyUV，）*，α至少含有一個非終結符，且βe（V，Ur，）"，則稱G為0型文法。對0型文法的每條產生式分別施加以下限制，則可得以下文法。

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

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

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

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

【備考點撥】

句子和語言。設有文法 G=（V，， V7， P，S）

推導與直接推導∶推導就是從文法的開始符號 S出發(fā)，反復使用產生式，將產生式左部的非終結符替換為右部的文法符號序列（展開產生式用→ 表示），直到產生一個終結符的序列時為止。

【相關試題】

簡單算術表達式的結構可以用下面的上下文無關文法進行描述(E為開始符號)，( )是符合該文法的句子。

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  www.pokkc.com/st/3961312318.html