欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

程序设计语言基础知识

程序员文章站 2022-03-26 23:02:58
编译过程 词法分析:对源程序从前到后(从左至右)逐个字符地扫描,从而识别出一个个"单词"符号。 语法分析:判断语法是否出错,如表达式、循环语句、程序等。 语义分析:检查如赋值语句左右是否匹配,是否有零除数等。 文法 G={Vt*Vn*S*P} Vt是一个非空有限的符号集合,它的每个元素称为终结符。 ... ......

编译过程

程序设计语言基础知识

词法分析:对源程序从前到后(从左至右)逐个字符地扫描,从而识别出一个个"单词"符号。

语法分析:判断语法是否出错,如表达式、循环语句、程序等。

语义分析:检查如赋值语句左右是否匹配,是否有零除数等。

文法

G={Vt*Vn*S*P}

Vt是一个非空有限的符号集合,它的每个元素称为终结符。

Vn是一个非空有限集合的符号,它的每个元素称为非总结符。

S称为文法G的开始符号。

P是一个非空有限集合,它的元素称为产生式。

1型文法:又称为上下文有关文法。

2型文法:又称为上下文无关文法。

3型文法:又称为正规文法,使用最多。

0型文法:短语文法。

有限自动机

计算机控制系统的控制程序具有有限状态自动机(FA)的特征,可以用有限状态机理论来描述。

确定有限自动机(DFA)

自动机的每个状态都有对字母表中所有符号的转移。

非确定有限自动机(NFA)

自动机的状态对字母表中的每个符号可以有也可以没有转移,对一个符号甚至可以有多个转移。

(1)确定的有限自动机DFA

S是一个有限状态集合。

是一个字母表,输入字符的集合。

f是从S*àS上的单值部分映像。f(A,a)=Q表示当前状态为A,输入为a时,将转换到下一状态Q,称Q为A的一个后继状态。

S0S,是唯一的初态。

ZS,是一个终态集。

已知有DFA M1=({s0,s1,s2,s3},{a,b},f,S,{s3})

程序设计语言基础知识

(2)不确定的有限自动机NFA

S是一个有限状态集合。

是一个字母表,输入字符的集合。

f是从S*àS上的单值部分映像。f(A,a)=Q表示当前状态为A,输入为a时,将转换到下一状态Q,称Q为A的一个后继状态。

S0S,是一个非空初态集。

ZS,是一个终态集。

正规式

下面文法G[S]它无法识别(D),次文法对应正规式为(C)。

G[S]:

SàaA|bB

AàbS|b

BàaS|a

(1)A.ababab    B.bababa    C.abbaab    D.babba

(2)A.(a|b)*    B.(ab)*        C.(ab|ba)*    D.(ab)*b*

解析:

SàaAàabSàabaAàababSà(ab)*

SàbBàbaSàbabBàbabaSà(ba)*

SàaAàabSàabbBàabbaSàabbaaAàabbaabà(ab|ba)*

下图所示为一个有限自动机(其中,A是初态,C是终态),该自动机识别的语言可用正规式(C)表示。

A.0000        B.1111        C.0101        D.1010

程序设计语言基础知识

对于以下编号为 jkl的正规式,正确的说法是(C)。

j(aa*|ab)*b        k(a|b)*b    l((a|b)*|aa)*b

A.正规式jk等价        B.正规式jl等价

C.正规式kl等价        D.正规式jkl互不等价

语法树

以图示化形式把句子分解成各个组成部分,以分析句子的语法结构。语法树表示法与文法规则完全一致。但更为直观和完整。

满足下列条件的数称为文法G的语法树:

(1)每个节点用G的一个终结符或非终结符标记。

(2)根结点用文法开始符号S标记。

(3)内部结点一定是非终结符。若某个内部结点A有n个分支,且其所有子节点从左至右依次标记为X1,X2,…,Xn,则AàX1,X2,…,Xn一定是G的一条产生式;

(4)若某一结点n至少有一个它自己除外的子孙,并且有标记A,则A一定在非终结符中。

程序设计语言基础知识

文法G=({a,b},{S,A},S,P),其中:SàaAS|a,AàSbA|SS|ba。请构造句型aabAa的推导树。

解析:

SàaASàa(SbA)Sàa(abA)a

程序设计语言基础知识

中间代码表达式

前缀表达式(+ab)

中缀表达式(a+b)

后缀表达式(ab+)

程序设计语言基础知识

例如,表达式(a-b)*(c+5)的后缀是(D)。

A.abc5+*-    B.ab-c+5*

C.abc-*5+    D.ab-c5+*

程序设计语言基础知识

解析:从左至右,从下至上。ab-c5+*