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

【考法分析】

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

【要點分析】

文法和語言的形式描述

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

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

1型文法∶ G的任何產(chǎn)生式α→β（S→ε除外）均滿足|q|≤8（|x表示x中文法符號的個數(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型文法也稱為短語文法，其功能相當于圖靈機，任何0型語言都是遞歸可枚舉的;反之，遞歸可枚舉集也必定是一個0型語言。1型文法也稱為上下文有關(guān)文法，這種文法意味著對非終結(jié)符的替換必須考慮上下文，并且一般不允許替換成ε串。

【備考點撥】

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

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

【相關(guān)試題】

簡單算術(shù)表達式的結(jié)構(gòu)可以用下面的上下文無關(guān)文法進行描述(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.jazzmuze.com/st/3961312318.html