67天通过软考（二）——程序语言小结

一、有限自动机(FA)

1.在正规式中，“*”号表示任意自我连接 (eg:a*表示n>=0个a (ab)*表示n>=0个ab相连ababab...)
2.将有限自动机M转化为与其等价的正规式R的步骤：
(1)在M的转换图中加上2个状态x和y，从x用标有e的弧连接到M的所有初态节点，从M的所有终态节点用标有e的弧连接到y，从而形成一个新的有穷自动机M'。它只有一个初态x和一个终态y，显然L(M)=L(M'),L(M)表示M所能接受的字符串集
(2)逐步消去所有节点，直到只剩下x和y为止，在消节过程中逐步用正规式来标记弧，消节的规则见下图

3.(R1|R2)*=(R1*R2*)*
4.正规式不能用于描述配对或嵌套的结构
  正规式只能表示给定结构的固定次数的重复或者没有给定次数的重复
  正规式描述的每种结构都可以用上下文无关文法描述，但反之则不然
  每个正规式都有一个与其等价的NFA
5.若某DFA与NFA等价，则它们可识别的记号相同
6.NFA与DFA的区别(1)f是上的映像。对于S中的一个给定状态及输入符号，返回一个状态的集合，即当前状态的后继状态不一定是唯一确定的。
(2)有向弧上的标记可以是

二、文法

1.文法的定义：
   描述语言语法结构的形式规则称为文法。文法G是一个四元组，可表示为,其中是一个非空有限集，其每个元素称为一个终结符；是一个非空有限集，其每个元素称为非终结符。和不含公共元素。令，称V为文法G的词汇表，V中的符号称为文法符号，包括终结符和非终结符。，称为开始符号，它至少要在一条产生式中作为左部出现。P是产生式的有限集合，每个产生式是形如“”的规则，其中称为产生式的左部，且中至少含有一个非终结符；称为产生式的右部，且
正则闭包+：
闭包*：
2.文法分类(1)短语文法(0型文法)
(2)上下文相关文法(1型文法)
(3)上下文无关文法(3型文法)
(4)正规(则)文法(3型文法)
上面四种文法有包含的关系，1型文法是0型文法的一个子集，2型文法是1型文法的一个子集，3型文法是2型文法的一个子集
3.上下文无关方法G所描述的语言是从S出发推导出的仅包含T中符号的串的集合

三、其他

1.语句用于描述程序中得运算步骤、控制结构及数据传输
  语法是书写规则
  语义表示含义
  语用是关于程序与使用者之间的关系
2.为什么叫共用体呢，因为不同的数据项在内存中占用同一段存储单元，且存储单元的大小以最大空间的变量为准
3.将高级语言编译后产生的仍然是一种程序(低级语言程序，如汇编)，只有当程序调入内存执行时，逻辑地址才会转换成物理地址