lexical analysis

发表于

lexical analysis

goals

converts from phsical description of a program into sequence of tokens. (token: one logical piece of the source file)

  • Each token associated with a lexeme
  • have opitional attributes

choosing good tokens

依赖于不同的语言：

选择关键词； 将lexeme分成不同组的id，如数字，字符串等； 丢弃无用的信息，如空格，注释等；

扫描的困难

  • 如何判断哪一个的lexeme对应于tokens
  • 有多种扫描方式来堆输入扫描，如何取舍
  • 如何高效获得想要的

正则表达式

定义：用来捕捉某些语言的一系列描述

符号ε用来匹配空字符串，符号a用来匹配a；

符合型：

  • 如果R1和R2是正则表达式，那么R1R2就表示R1R2的级联；
  • 如果R1和R2是正则表达式，那么R1|R2就表示R1和R2任意取一个；
  • 如果R是正则表达式，那么R*就表示R的闭包；

实现正则表达式

正则表达式能通过有限自动机来实现。

而有限自动机有两种： NFA(nondeterministic finite automa) DFA(deterministic finite automa)

以图表示的话，圆圈表示状态，箭头表示转移，双圆圈表示结束: img

如果一个状态有多个transitions，那么多条transitions都要进行。

Epsilon transition: 不消耗任何输入,但会进行transitions。 img

Simulating an NFA

  1. 有限初始化，追踪开始状态和所有可以通过ε转移到达的状态；
  2. 对于输入的每一个字符
  • 维持一个集合表示下一个状态，初始为空
  • 对于每一个当前状态，跟踪针对输入字符可以到达的状态,并添加进集合中
  1. 添加可以新状态集合中通过ε的状态

解决匹配冲突

通常情况下选择最长match.

具体做法是，将所有正则表达式转化为NFA，然后合并成一个状态机，扫描输入，记录上一个已知的匹配。选择更高优先级的。

DFA

与NFA不同，DFA的每一个状态只有一个与某个字符相关的转移，并且没有ε transitions

img
  • Make the DFA simulate the NFA

(q0是开始状态)

Step 1: Initially Q’ = ɸ.

Step 2: Add q0 to Q’.

Step 3: For each state in Q’, find the possible set of states for each input symbol using transition function of NFA. If this set of states is not in Q’, add it to Q’.

Step 4: Final state of DFA will be all states with contain F (final states of NFA)

参考资料：https://www.geeksforgeeks.org/theory-of-computation-conversion-from-nfa-to-dfa/