程序设计语言基础知识

编译过程

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

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

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

文法

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+*

 

 

原文地址:https://www.cnblogs.com/yinshoucheng-golden/p/8727060.html