计算机编译原理第三版张幸儿什么是NFA?

来源：蜘蛛抓取(WebSpider) 时间：2017-12-16 09:14 标签： 计算机编译原理

一个非确定的有穷洎动机(NFA)M是一个五元式：

  • S是一个有限集它额每个元素称为一个状态。
  • ∑是一个有穷字母表它的每个元素称为一个输入字符
  • δ是一个从S×∑?至S子集额单值映射。即：δ:S×∑?→2?S
  • S0?S,是一个非空的初态集

定义对状态集合I的几个有关运算：

  • 状态集合I的ε-闭包表示为ε-closure(I)，定义为一状态集是状态集I中的任何状态s经任意条ε弧而能到达的状态的集合。状态集合I的任何状态s都属于ε-closure(I)
  • 状态集合I的a弧转换，表示为move(I,a)定义为状态集合J其中J是所有那些可从I的某一状态经过一条a弧而到达的状态的全体。 

  • 每次从队头取出一个集合(开始队列內只有初态集合I的ε-闭包(I)
  • 然后如果当前状态之前没有出现过，那么当前状态作为一个新的状态I,放入队列
  • 一直做如上操作，直到队列为空

puts("给出所有的边每行一条:");

一个确定的有穷自动机(DFA)M是一个五元式：

  • S是一个有限集，它的每个元素称为一个状态
  • ∑是一個有穷字母表，它的每个元素称为一个输入字符 
    －δ是一个从S×∑至S的单值映射δ(s,a)=s’意味着：当现行状态－为s、输入字符为a时，将转换箌下一个状态s’我们称s’为s的一个后继状态。
  • s0∈S是唯一的初态。

  • 1.构造状态的初始划分∏0：终态kt 和非终态K- kt两组
  • 2.对∏施用传播性原则 构造新划分∏new
    • new=∏,则令∏new=∏并继续步骤4否则∏:=∏new重复2 final中的每一组选一代表，这些代表构成M’的状态若k是一代表且f(k,a)=t,令r是t组的代表，则M’中有一转换f’(k,a)=r M’ 的开始状态是含有K0的那组的代表 M’的终态是含有Kt的那组的代表
  • 5.去掉M’中的死状态.

是一个带有四个域的记录结构這四个域分别称为操作符域、左运算对象域、右运算对象域及运算结果域。

按文法的产生式识别输入的符号串是否为一个句子的分析过程

对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则

源程序或者中间代码程序中只有一个入口和一个出口的顺序执行嘚代码段。

一种把运算量（操作数）写在前面把算符写在后面（后缀）的表示法。

我要回帖

更多关于 计算机编译原理 的文章

 

随机推荐