LEX 生成的词法分析器的执行：最长匹配原则
传递单词的属性，是把属性值赋给全程变量 yylval
正规定义式：
if  if
then  then
else  else
relop  < | <= | = | <> | > | >=
id  letter(letter|digit)*
num  digit+(.digit+)?(E(+|-)?digit+)?

```C
相应的LEX源程序
/*定义部分 */
%{
/* C语言描述的标识符常量的定义，如LT、LE、EQ、NE、GT、GE、IF、THEN、ELSE、ID、NUMBER、RELOP */
extern yylval;
%}
/* 正规定义式 */
delim     [  \t\n]
ws        {delim}+
letter    [A-Za-z]
digit     [0-9]
id        {letter}({letter}|{digit})*
num       {digit}+(\.{digit}+)?(E[+\-]?{digit}+)?
%%
/* 规则部分 */
{ws}          {/* 没有动作，也不返回 */}
if            { return(IF); }
then          { return(THEN); }
else          { return(ELSE); }
{id}          { yylval=install_id(); return(ID); }
{num}         { yylval=install_num(); return(NUMBER); }
“<”            { yylval=LT; return(RELOP); }
“<=”           { yylval=LE; return(RELOP); }
“=”            { yylval=EQ; return(RELOP); }
“<>”           { yylval=NE; return(RELOP); }
“>”            { yylval=GT; return(RELOP); }
“>=”           { yylval=GE; return(RELOP); }
%%
/* 辅助过程 */
install_id() {
  /*  把单词插入符号表并返回指针，
      yytext指向该单词的第一个字符，
      yyleng给出它的长度  */
}
install_num() {
    /* 类似于上面的过程，但单词是常数 */
}

```


当 digit 为标识符时， digitlexval 为 digit 在符号表中的入口； 当 digit 为常数时， digitlexval 为 digit 在常数表中的入口 这个符号表和常数表是什么？是在词法分析后建立的吗

您提到的 `digit·lexval` 在**编译原理**的语义分析或中间代码生成阶段是一个典型的设计，用于表示词法分析后单词（token）的附加信息。我来解释一下符号表和常数表，以及它们在编译过程中的位置和用途。

---

## 1. 符号表和常数表的定义

### **符号表（Symbol Table）**

- 存放程序中**标识符（identifier）** 的相关信息，比如变量名、函数名、类型名等。
    
- 表项通常包括：
    
    - 名字（字符串）
        
    - 类型（int, float, struct…）
        
    - 作用域
        
    - 存储位置/地址
        
    - 如果是函数，则还有参数列表等信息
        
- 在您的上下文中，`digit` 如果是一个**标识符**（例如程序员定义的变量名为 `digit`），那么 `digit·lexval` 就指向**符号表**中该标识符对应的入口（表项编号或指针），从而能查到它的属性。
    

---

### **常数表（Literal Table / Constant Table）**

- 存放程序中出现的**常量值（literals）**，例如 `3.14`、`42`、`"hello"` 等。
    
- 词法分析器遇到一个数字常量（如 `123`）时，会把它转换成内部形式（比如整数或浮点数），并存入常数表。
    
- 常数表的好处：
    
    - 节省内存：相同的常量只存一次。
        
    - 便于优化和代码生成。
        
- 在您的上下文中，如果 `digit` 是一个**数字常量**（例如词法分析得到的整型常数 token），那么 `digit·lexval` 就指向**常数表**中该常量的入口。
    

---

## 2. 建立时机

### **词法分析阶段（Lexical Analysis）**

- 识别出一个个 token，并区分它是**标识符**还是**常数**。
    
- 如果是标识符，会在**符号表**中查找（或创建）对应的表项，并把该表项位置（索引或指针）赋给该 token 的 `lexval` 属性。
    
- 如果是数字常数，会在**常数表**中查找（或创建）对应的表项，并把该表项位置赋给该 token 的 `lexval` 属性。
    
- 所以**词法分析阶段已经初步填充符号表和常数表**（至少把名字或常量值放进去），但它们的完整类型信息等通常要等到**语法分析**和**语义分析**阶段才补充完整。
    

---

### **后续阶段更新**

- **语法分析**（Syntax Analysis）：构建语法树，传递 token 及其属性（包括 `lexval`）。
    
- **语义分析**（Semantic Analysis）：利用符号表和常数表检查类型、作用域、进行常量折叠等。
    

---

## 3. 示例

假设源代码：

c

int a = 5;

词法分析得到 tokens：

- `int`（关键字）
    
- `a`（标识符）
    
- `=`（运算符）
    
- `5`（整数常量）
    

过程：

1. 遇到标识符 `a`：查符号表，没有则创建新条目，位置为 `sym_addr_a`，把 `a` 的 `lexval` 设为 `sym_addr_a`。
    
2. 遇到常量 `5`：查常数表，没有则创建，位置为 `const_addr_5`，把 `5` 的 `lexval` 设为 `const_addr_5`。
    
3. 后续语义分析阶段：将 `a` 的类型 `int` 填入符号表的对应条目，并可能将 `5` 的常量值用于初始化代码生成。
    

---

## 4. 为什么分开两个表？

1. **类型与用途不同**
    
    - 标识符有作用域、类型、存储类别等复杂属性。
        
    - 常量值只需存储值本身，可能还有类型（整型、浮点型、字符串），没有作用域变化。
        
2. **管理效率**
    
    - 常数表可以更简单，可能按值哈希或排序；符号表需要按作用域层次管理。
        
3. **优化与常量池**
    
    - 常数表在目标代码生成时可以直接变成常量池（如汇编中的 `.data` 节或 Java class 文件的 constant_pool）。
        

---

## 总结

|表|存储内容|填充时机（开始）|用途|
|---|---|---|---|
|符号表|标识符的名字、类型、作用域等|词法分析首次遇到标识符时创建条目，语义分析补充属性|用于变量/函数的查找与类型检查|
|常数表|程序中出现的常量值|词法分析遇到常量时创建条目|存储字面量，便于统一引用与优化|

因此，`digit·lexval` 是 token 的一个属性，根据 `digit` 是标识符还是常数，指向不同表的入口，这是编译器中常见的设计。

具体把表格画出说明可以吗》

# 符号表 vs 常数表 详细对比表格

## 表结构对比

|**属性**|**符号表（Symbol Table）**|**常数表（Constant Table）**|
|---|---|---|
|**存储内容**|程序中的标识符（变量名、函数名、类名等）|程序中的字面常量（数字、字符串、字符等）|
|**条目结构**|||
||1. 名字（字符串）|1. 常量值（整数、浮点数、字符串等）|
||2. 类型（int, float, array 等）|2. 常量类型（int_const, float_const, string_const 等）|
||3. 作用域（全局、局部、参数等）|3. 内部表示值（已转换的二进制形式）|
||4. 存储位置/地址（相对地址）|4. 引用次数（用于优化）|
||5. 维度信息（数组）|5. 目标代码中的地址（代码生成后）|
||6. 参数列表（函数）||
|**数据结构**|哈希表 + 作用域栈（支持嵌套作用域）|哈希表（按值哈希）或有序表|
|**主要操作**|插入、查找（带作用域）、删除（作用域退出时）|插入、查找（按值）|

## 建立时机与流程对比

## 具体示例分析

### 示例代码

c

int main() {
    int digit = 123;
    int sum = digit + 456;
    return 0;
}

### 词法分析后的 token 流

|Token|类型|lexval 指向|
|---|---|---|
| `int` |关键字|-|
| `main` |标识符|符号表入口#1|
| `(` |标点|-|
| `)` |标点|-|
| `{` |标点|-|
| `int` |关键字|-|
| `digit` |标识符|符号表入口#2|
| `=` |运算符|-|
| `123` |整数常量|常数表入口#1|
| `;` |标点|-|
| `int` |关键字|-|
| `sum` |标识符|符号表入口#3|
| `=` |运算符|-|
| `digit` |标识符|符号表入口#2|
| `+` |运算符|-|
| `456` |整数常量|常数表入口#2|
| `;` |标点|-|
| `return` |关键字|-|
| `0` |整数常量|常数表入口#3|
| `;` |标点|-|
| `}` |标点|-|

### 符号表内容（语义分析后）

|地址|名字|类型|作用域|存储地址|其他属性|
|---|---|---|---|---|---|
|#1| `main` | `function` |全局|0 x 1000|返回类型:int, 参数:无|
|#2| `digit` | `int` |main 函数内|局部偏移-4|初始值:123|
|#3| `sum` | `int` |main 函数内|局部偏移-8|初始值:未知|

### 常数表内容（词法分析后）

|地址|常量值|类型|内部表示|引用次数|
|---|---|---|---|---|
|#1| `123` |整数常量|0 x 7 B|1|
|#2| `456` |整数常量|0 x 1 C 8|1|
|#3| `0` |整数常量|0 x 0|1|

## 重要特性总结表

|**特性**|**符号表**|**常数表**|
|---|---|---|
|**重复条目**|同一作用域不允许重复名字，不同作用域可以|相同值只存储一次，重复使用同一入口|
|**生命周期**|与标识符作用域相关，退出作用域时可删除|整个程序生命周期都存在|
|**变化性**|条目属性可能变化（如类型检查后）|创建后内容不变|
|**查询方式**|按名字 + 作用域链查找|按值查找|
|**优化作用**|用于类型检查、作用域分析|用于常量传播、常量折叠、共享存储|
|**目标代码**|生成变量地址分配|生成常量池/数据段内容|

## 为什么需要两个不同的表？

### 设计哲学差异：

1. **符号表**是 **"名字→属性"** 的映射
    
    - 关心的是名字的声明和使用
        
    - 需要处理重名（不同作用域）
        
    - 需要跟踪类型变化
        
2. **常数表**是 **"值→位置"** 的映射
    
    - 关心的是值的唯一性和重用
        
    - 相同的值只存储一次
        
    - 便于生成高效的目标代码
        

### 编译器中的实际实现：

c

// 简化的 token 结构
typedef struct {
    int token_type;      // 如 IDENTIFIER, INTEGER_CONST
    union {
        int sym_index;   // 符号表索引（当 token_type=IDENTIFIER）
        int const_index; // 常数表索引（当 token_type=INTEGER_CONST）
    } lexval;            // 词法值
    char *lexeme;        // 原始字符串
} Token;
// 词法分析时的处理
Token get_next_token() {
    // 识别数字
    if (isdigit(current_char)) {
        int value = parse_number();
        int const_index = add_to_constant_table(value);
        return make_token(INTEGER_CONST, const_index);
    }
    // 识别标识符
    else if (isalpha(current_char)) {
        char *name = parse_identifier();
        int sym_index = lookup_symbol_table(name);
        return make_token(IDENTIFIER, sym_index);
    }
    // ...
}

这种分离设计让编译器各个阶段的职责更清晰，也便于优化和错误处理。

属性和属性值的区别是什么

# 属性 vs 属性值 详细解析

## 核心区别：定义与角色

|**对比维度**|**属性（Attribute）**|**属性值（Attribute Value）**|
|---|---|---|
|**本质**|**名字/标签** - 描述特征的名词|**具体内容** - 属性的实际数据|
|**类比**|表格的**列标题**|表格的**单元格内容**|
|**变化性**|通常是固定的、预定义的|会随着不同实体而变化|
|**示例**|"颜色"、"年龄"、"价格"|"红色"、25、"99.99 元"|

## 具体示例分析

### 1. 在符号表条目中

c

// 符号表条目结构
struct SymbolTableEntry {
    char *name;           // 标识符名字 - 这是一个属性
    char *type;           // 类型属性 - 属性名
    int scope_level;      // 作用域属性 - 属性名
    int memory_offset;    // 存储偏移属性 - 属性名
    // ...
};
// 具体的符号表实例
SymbolTableEntry entry = {
    .name = "digit",      // "name"属性的值是"digit"
    .type = "int",        // "type"属性的值是"int"  
    .scope_level = 1,     // "scope_level"属性的值是 1
    .memory_offset = -4   // "memory_offset"属性的值是-4
};

### 2. 在常数表条目中

c

// 常数表条目结构  
struct ConstantTableEntry {
    int const_type;       // 常量类型属性
    union {
        int int_val;      // 整数值属性
        float float_val;  // 浮点值属性
        char *str_val;    // 字符串值属性
    } value;              // 值属性
    int ref_count;        // 引用计数属性
};
// 具体的常数表实例
ConstantTableEntry entry = {
    .const_type = INTEGER_CONST,  // "const_type"属性的值是 INTEGER_CONST
    .value.int_val = 123,         // "value"属性的值是 123
    .ref_count = 2                // "ref_count"属性的值是 2
};

## 分类对比表

### 语法层面

|**层面**|**属性**|**属性值**|
|---|---|---|
|**定义**|结构体/类的**成员变量名**|成员变量的**具体赋值**|
|**示例**| `student.age` (age 是属性)| `student.age = 20` (20 是属性值)|
|**位置**|在源代码中固定定义|运行时动态确定|

### 数据库层面

|**概念**|**属性**|**属性值**|
|---|---|---|
|**关系**|表的**列/字段**|行的**单元格数据**|
|**示例表**|学生表(学号,姓名,成绩)|(2023001,"张三",95)|
|**SQL**| `CREATE TABLE` 中定义| `INSERT INTO` 中指定|

### 编译原理中的应用

## 属性文法（Attribute Grammar）中的体现

### 属性文法定义

- **属性**：与文法符号相关的语义信息
    
- **属性值**：该语义信息的具体取值
    

### 示例：简单赋值语句

text

产生式：        E → E 1 + T
语义规则：      E.val = E 1.val + T.val

- **属性**：`.val`（值属性）
    
- **属性值**：`E1.val` 的具体数值，如 42
    

### 属性依赖图

text

        E.val
        /   \
       /     \
    E1.val   T.val
    (42)     (10)
    
最终：E.val = 52  ← 属性值

## 关键区别总结表

|**特征**|**属性**|**属性值**|
|---|---|---|
|**抽象层级**|抽象特征描述|具体数据实例|
|**数量关系**|一个实体有多个属性|每个属性有一个当前值|
|**设计阶段**|设计时确定（有哪些属性）|运行时确定（具体值是多少）|
|**可变性**|通常不变（结构固定）|经常变化（数据更新）|
|**存储方式**|结构定义、元数据|实际数据、实例状态|
|**访问方式**|通过名字引用|通过属性名获取当前值|

## 实际编译器中的例子

### 1. 词法分析阶段

c

// Token 的属性定义
typedef struct {
    // 以下是属性（成员变量）
    TokenType type;       // 属性：token 类型
    int line_no;          // 属性：行号
    union {
        int sym_idx;      // 属性：符号表索引（当 type 是标识符时）
        int const_idx;    // 属性：常数表索引（当 type 是常量时）
        // 注意：sym_idx 和 const_idx 是同一存储位置的不同属性名
    } value;              // 属性：值信息
} Token;
// Token 的具体实例（属性值）
Token token 1 = {
    .type = IDENTIFIER,      // type 属性的值：IDENTIFIER
    .line_no = 10,           // line_no 属性的值：10
    .value.sym_idx = 5       // value.sym_idx 属性的值：5
};
Token token 2 = {
    .type = INTEGER_CONST,   // type 属性的值：INTEGER_CONST  
    .line_no = 10,           // line_no 属性的值：10
    .value.const_idx = 3     // value.const_idx 属性的值：3
};

### 2. 重要的区分场景

**场景**：`digit·lexval` 的含义

- **当 digit 是标识符时**：
    
    - `lexval` 是属性名（表示"词法值"）
        
    - `digit·lexval` 的值是指向符号表的指针（属性值）
        
- **当 digit 是常数时**：
    
    - `lexval` 是同样的属性名
        
    - `digit·lexval` 的值是指向常数表的指针（属性值）
        

**关键点**：相同的属性名（lexval），不同类型的 token 具有不同**含义的属性值**。

## 记忆技巧

1. **英语角度**：
    
    - 属性：Attribute/Property（是什么）
        
    - 属性值：Value of attribute（是多少）
        
2. **编程角度**：
    
    java
    
    // 类定义 - 属性
    class Student {
        String name;    // 属性：名字
        int age;        // 属性：年龄
    }
    // 对象实例 - 属性值  
    Student s = new Student();
    s.name = "张三";    // "张三"是 name 属性的值
    s.age = 20;         // 20 是 age 属性的值
    
3. **日常类比**：
    
    - 属性：人的"身高"、"体重"、"姓名"
        
    - 属性值：175 cm、70 kg、"李四"
        

这种区分在编译原理中尤为重要，因为编译器需要在不同阶段为同一属性名填充不同的属性值，完成从源代码到目标代码的转换。

属性可以是任何对象: 符号串、数字、类型、内存单元或其他对象 。为什么说属性还可以是数字？

# 属性为什么可以是数字：深入解析

您提出的问题非常好！这里的表述确实有些微妙，需要仔细区分。让我们一步步澄清。

## 1. 核心澄清：两种不同的"数字"含义

当我们说"属性可以是数字"时，实际上有两种可能的理解：

|**理解角度**|**含义**|**示例**|
|---|---|---|
|**作为属性名**|数字本身作为属性的标识/标签|数组元素：`arr[0]`、`arr[1]` 中的 0、1|
|**作为属性值**|数字作为某个属性的具体取值|符号表的 `scope_level = 2` |

通常，在编译原理上下文中，**属性是名字/标签**，而**属性值是具体数据**（包括数字）。但确实存在特殊情况。

## 2. 属性作为数字的特殊情况

### 2.1 数组索引作为属性名

c

// 数组元素的表示
struct ArrayElement {
    int index;      // 索引属性：这是一个数字作为属性名
    int value;      // 值属性：具体存储的值
};
// 实际上更常见的表示
ArrayElement arr[] = {
    {0, 100},  // 索引 0 处的值为 100
    {1, 200},  // 索引 1 处的值为 200
    {2, 300}   // 索引 2 处的值为 300
};

这里**数字作为索引属性的值**，而不是属性本身。但有些人可能会简称为"数字属性"。

### 2.2 中间代码中的位置属性

llvm

; LLVM 中间代码示例
%1 = add i 32 5, 3    ; %1 是虚拟寄存器（属性是寄存器编号）
%2 = mul i 32 %1, 2   ; %2 是另一个虚拟寄存器

这里的 `%1`、`%2` 可以看作是以数字为标签的属性名。

## 3. 更准确的表述应该是...

原文"属性可以是任何对象：符号串、数字、类型、内存单元或其他对象"可能是在一个更宽泛的语境中说的。让我们重新精确表述：

## 4. 编译原理中的实际例子

### 4.1 错误的混淆 vs 正确的理解

|**可能混淆的说法**|**更准确的说法**|**示例**|
|---|---|---|
|"scope 是一个数字属性"|"scope_level 属性的值是数字"| `符号表条目.scope_level = 2` |
|"值是一个数字属性"|"value 属性的值是数字"| `常数表条目.value = 123` |
|"地址是一个数字属性"|"address 属性的值是内存地址（数字）"| `符号表条目.address = 0x1000` |

### 4.2 实际数据结构表示

c

// 符号表条目
typedef struct {
    // 属性定义（这些是属性名）
    char *name;          // 属性：标识符名字
    Type *type;          // 属性：类型信息
    int scope_level;     // 属性：作用域层次
    int offset;          // 属性：存储偏移
    
    // 属性值的类型说明：
    // name属性的值：字符串（如"digit"）
    // type属性的值：Type对象指针
    // scope_level属性的值：整数（如2）
    // offset属性的值：整数（如-4）
} SymbolEntry;
// 常数表条目
typedef struct {
    // 属性定义
    ConstantType const_type;  // 属性：常量类型
    union {
        int int_val;          // 属性：整数值（当 const_type 为 INT 时）
        float float_val;      // 属性：浮点值（当 const_type 为 FLOAT 时）
        char *str_val;        // 属性：字符串值（当 const_type 为 STRING 时）
    } value;                  // 属性：值
    
    // 属性值的例子：
    // const_type属性的值：INTEGER_CONST（枚举值，本质是数字）
    // value.int_val属性的值：123（数字）
} ConstantEntry;

## 5. 为什么会有这种混淆？

### 5.1 术语的模糊使用

- 在某些编程语言中（如 Python），对象的属性（attribute）可以是任何值
    
- 但在编译原理的上下文，特别是属性文法中，属性有更明确的定义
    

### 5.2 英语表达问题

- "Attribute can be a number" 可能被误解
    
- 更准确："The value of an attribute can be a number"
    

### 5.3 具体例子澄清

**正确理解**：

text

符号表条目:
  属性名: scope_level
  属性值: 2 (数字)
  
  属性名: type
  属性值: int_type (类型对象)
  
  属性名: address  
  属性值: 0 x 1000 (数字表示的内存地址)

## 6. 结论：应该如何理解

### 6.1 在标准属性文法中

- **属性**是文法符号的语义特征名（如 `.val`, `.type`, `.addr`）
    
- **属性值**是这些特征的具体取值
    
- 属性值可以是：数字、字符串、类型、内存地址等
    

### 6.2 在您引用的原文中

原文可能的意思是：  
"**属性值**可以是任何对象：符号串、数字、类型、内存单元或其他对象"

而不是：  
"**属性本身**可以是任何对象"

### 6.3 实用的记忆方法

text

编译器中常见的属性-值对：
1. 名字属性：
   - 属性名: name
   - 属性值: "digit" (字符串)
2. 类型属性：
   - 属性名: type  
   - 属性值: INT_TYPE (类型对象/枚举)
3. 作用域属性：
   - 属性名: scope_level
   - 属性值: 2 (数字)
4. 地址属性：
   - 属性名: address
   - 属性值: 0 x 1000 (数字)
1. 值属性：
   - 属性名: value
   - 属性值: 123 (数字)

**关键点**：属性本身是**特征的名字**（通常是字符串标识符），而这个特征的**具体取值**可以是数字、字符串、类型等各种对象。

因此，当看到"属性可以是数字"时，最好理解为"属性的值可以是数字"，除非在非常特定的上下文中（如数组索引作为属性名）。



为什么是 LL(1)和 LR(0),



---

## 1. **LL(1)**

这是**自顶向下**语法分析中的概念。

- **第一个 L**：从左到右扫描输入字符串（Left-to-right scanning）。
    
- **第二个 L**：最左推导（Leftmost derivation）。
    
- **(1)**：向前看 1 个符号来决定使用哪个产生式。
    

**为什么是 1**：  
因为 LL(1) 文法在每一步推导时，只需要查看当前输入的下一个终结符（即 lookahead 长度为 1），就可以决定使用哪个产生式。  
数字 1 表示预测时所需的 lookahead 符号数量，也可以推广到 LL(k)（看 k 个符号）。

---

## 2. **LR(0)**

这是**自底向上**语法分析中的概念。

- **L**：从左到右扫描输入。
    
- **R**：最右推导的逆序（Rightmost derivation in reverse）。
    
- **(0)**：在分析时**不需要向前查看输入符号**（即 lookahead 长度为 0）来决定动作（移进或规约）。
    

但是 LR(0) 在实际中限制很大，容易产生**移进-规约冲突**或**规约-规约冲突**，所以实际常用 **SLR(1)、LR(1)、LALR(1)**，括号里的 1 表示向前看 1 个符号。

---


##  **总结差异**

|类型|推导方式|向前看长度|能力/说明|
|---|---|---|---|
|LL(1)|自顶向下|1 个符号|不能处理左递归，较简单。|
|LR(0)|自底向上|0 个符号|容易有冲突，实际很少直接用。|
|LR(1)|自底向上|1 个符号|分析能力强，但分析表大。|
|SLR(1)|自底向上(SLR)|1 个符号|比 LR(0) 多考虑 FOLLOW 集解决冲突。|

---