上一节:
下一节:

  编译器设计 - 词法分析

  • 简述

    词法分析是编译器的第一阶段。它从以句子形式编写的语言预处理器获取修改后的源代码。词法分析器通过删除源代码中的任何空格或注释将这些语法分解为一系列标记。
    如果词法分析器发现一个标记无效，它会产生一个错误。词法分析器与语法分析器密切合作。它从源代码中读取字符流，检查合法标记，并在需要时将数据传递给语法分析器。

  • 代币

    词位被称为标记中的字符序列（字母数字）。有一些预定义的规则可以将每个词位识别为有效标记。这些规则由语法规则通过模式定义。模式解释了什么可以是标记，这些模式是通过正则表达式定义的。
    在编程语言中，关键字、常量、标识符、字符串、数字、运算符和标点符号都可以被视为标记。
    例如，在 C 语言中，变量声明行 
    

int value = 100;
    包含令牌： 
    

int (keyword), value (identifier), = (operator), 100 (constant) and ; (symbol).

  • 代币规格

    让我们了解语言理论如何承担以下术语：

    字母表

    任何有限的符号集 {0,1} 是一组二进制字母，{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}是一组十六进制字母，{az, AZ} 是一组英文字母。

    字符串

    任何有限的字母（字符）序列都称为字符串。字符串的长度是字母出现的总数，例如字符串jc2182的长度是14，用|jc2182|表示 = 14. 没有字母的字符串，即长度为零的字符串称为空字符串，用ε (epsilon) 表示。

    特殊符号

    典型的高级语言包含以下符号：-
    算术符号 加法(+)、减法(-)、取模(%)、乘法(*)、除法(/)
    标点 逗号 (,)、分号 (;)、点 (.)、箭头 (->)
    任务 =
    特殊任务 +=, /=, *=, -=
    比较 ==, !=, <, <=, >, >=
    预处理器 #
    位置说明符 &
    逻辑的 &, &&, |, ||, !
    移位运算符 >>、>>>、<<、<<<

    语

    一种语言被认为是一些有限字母集上的有限字符串集。计算机语言被认为是有限集，并且可以对它们执行数学上的集合操作。有限语言可以通过正则表达式来描述。

  • 常用表达

    词法分析器只需要扫描和识别属于手头语言的有效字符串/标记/词位的有限集合。它搜索由语言规则定义的模式。
    正则表达式具有通过为有限的符号串定义模式来表达有限语言的能力。正则表达式定义的文法称为regular grammar. 由正则文法定义的语言称为regular language.
    正则表达式是指定模式的重要符号。每个模式都匹配一组字符串，因此正则表达式用作一组字符串的名称。编程语言标记可以用常规语言来描述。正则表达式的规范是递归定义的一个例子。正则语言易于理解并具有高效的实现。
    正则表达式遵循许多代数定律，可用于将正则表达式操作为等价形式。

  • 运营

    对语言的各种操作是：
    • 两种语言 L 和 M 的并集写成
      LUM = {s | s 在 L 中或 s 在 M 中}
    • 两种语言 L 和 M 的连接写成
      LM = {st | s 在 L 中，t 在 M 中}
    • 语言 L 的 Kleene 闭包写成
      L* = 语言 L 出现零次或多次。

  • 符号

    如果 r 和 s 是表示语言 L(r) 和 L(s) 的正则表达式，那么
    • Union: (r)|(s) 是表示 L(r) UL(s) 的正则表达式
    • Concatenation: (r)(s) 是表示 L(r)L(s) 的正则表达式
    • Kleene closure: (r)* 是表示 (L(r))* 的正则表达式
    • (r) 是表示 L(r) 的正则表达式

  • 优先级和关联性

    • *、连接 (.) 和 | （管道符号）是左关联的
    • * 具有最高优先级
    • 连接 (.) 具有第二高的优先级。
    • | （管道符号）的优先级最低。

    用正则表达式表示一种语言的有效标记

    如果 x 是正则表达式，则：
    x* 表示 x 出现零次或多次。
    即可以生成{ e, x, xx, xxx, xxxx, ... }
    x+ 表示 x 出现一次或多次。
    即，它可以生成 { x, xx, xxx, xxxx … } 或 xx*
    X？表示最多出现一次 x
    即，它可以生成 {x} 或 {e}。
    [az] 是英文的所有小写字母。
    [AZ] 是英文的全部大写字母。
    [0-9] 是数学中使用的所有自然数字。

    使用正则表达式表示符号的出现

    字母 = [a – z] 或 [A – Z]
    数字 = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 或 [0-9]
    符号 = [ + | - ]

    使用正则表达式表示语言标记

    小数=（符号）？(数字) +
    标识符=（字母）（字母|数字）*
    词法分析器剩下的唯一问题是如何验证用于指定语言关键字模式的正则表达式的有效性。一个广为接受的解决方案是使用有限自动机进行验证。

  • 自动完成

    有限自动机是一种状态机，它以一串符号作为输入并相应地改变其状态。有限自动机是正则表达式的识别器。当将正则表达式字符串输入有限自动机时，它会更改每个文字的状态。如果输入字符串被成功处理并且自动机达到其最终状态，则它被接受，即刚刚输入的字符串被认为是手头语言的有效标记。
    有限自动机的数学模型包括：
    • 有限状态集 (Q)
    • 有限输入符号集 (Σ)
    • 一个开始状态 (q0)
    • 最终状态集 (qf)
    • 过渡函数 (d)
    转移函数 (δ) 将有限状态集 (Q) 映射到有限输入符号集 (Σ)，Q × Σ ➔ Q

    有限自动机构造

    令 L(r) 是某种有限自动机 (FA) 识别的常规语言。
    • States: FA 的状态用圆圈表示。州名都写在圆圈里面。
    • Start state：自动机开始的状态，称为开始状态。开始状态有一个指向它的箭头。
    • Intermediate states：所有中间状态至少有两个箭头；一个指着，另一个指着他们。
    • Final state：如果输入字符串被成功解析，自动机应该处于这种状态。最终状态由双圆圈表示。它可能有任何奇数个指向它的箭头和偶数个指向它的箭头。奇数箭头的数量比偶数大一，即odd = even+1.
    • Transition：从一种状态到另一种状态的转换发生在输入中找到所需符号时。转换后，自动机可以移动到下一个状态或保持相同的状态。从一种状态到另一种状态的移动显示为有向箭头，其中箭头指向目标状态。如果自动机保持相同的状态，则绘制一个从状态指向自身的箭头。
    Example：我们假设 FA 接受任何以数字 1 结尾的三位二进制值。FA = {Q(q 0 , q f ), Σ(0,1), q 0 , q f , δ}

    最长匹配规则

    当词法分析器读取源代码时，它会逐字扫描代码；当出现空格、运算符符号或特殊符号时，它决定一个单词完成。
    For example: 
    

int intvalue;
    在扫描两个词位直到 'int' 时，词法分析器无法确定它是关键字int还是标识符 int 值的首字母。
    最长匹配规则指出，扫描的词位应根据所有可用标记中最长的匹配来确定。
    词法分析器也遵循rule priority其中，一种语言的保留字，例如关键字，优先于用户输入。也就是说，如果词法分析器找到与任何现有保留字匹配的词素，它应该生成错误。
上一节:
下一节: