UVa 309 FORCAL

题目描述

FORCAL\texttt{FORCAL}FORCAL是一种编程语言，其语法定义如下：

• 唯一的数据类型是整数
• 所有标识符隐式声明，长度不超过323232个字符
• 标识符由字母、数字和下划线组成，且至少有一个字符不是数字
• 字面量（整数常量）是最多888位的数字字符串
• 注释以--开头，到行尾结束
• 语句类型包括：
  • 赋值语句：(identifier) := (expression)
  • 输入/输出语句：read(List of identifiers);或write(List of expressions);
• 表达式由标识符、字面量、运算符+、-和括号组成
• 每个语句以分号;结束
• FORCAL\texttt{FORCAL}FORCAL不区分大小写
• 保留字：begin、end、read、write

词法规则：

• FORCAL\texttt{FORCAL}FORCAL标记（token\texttt{token}token）包括：标识符、字面量、符号(、)、+、-、:、=、:=、;、,
• 标记之间允许有空格、制表符、换行符
• 注释不是标记
• 连续的标识符、字面量或保留字必须用空白字符分隔
• 标记内部不允许包含空白字符

要求：编写程序读取输入文本，识别其中的FORCAL\texttt{FORCAL}FORCAL标记，每个标记输出一行。如果遇到既不是标记、也不是注释、也不是空白字符的字符串，则输出TOKEN ERROR，然后跳过当前块，继续处理下一个块。

输入格式

输入文件由多个文本块组成。每个块包含若干行文本，以一个空行结束。

输出格式

输出文件由与输入块对应的块组成。每个块中，每行输出一个识别出的标记，标记以与输入完全相同的格式输出。如果遇到错误，输出TOKEN ERROR并跳过当前块。每个输出块后输出一个空行。

样例输入

A1 := A + (- B); A123 A123 01.2 A B C := A beGIn aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

样例输出

A1 := A + ( - B ) A123 A123 01 TOKEN ERROR A beGIn TOKEN ERROR

题目分析

问题的本质

这是一个词法分析器（lexer\texttt{lexer}lexer或tokenizer\texttt{tokenizer}tokenizer）的实现问题。需要从输入的字符流中识别出符合FORCAL\texttt{FORCAL}FORCAL语法规范的标记，并处理错误情况。

核心挑战：

1. 识别多种类型的标记：标识符、字面量、运算符、分隔符
2. 处理注释（--到行尾）
3. 处理空白字符（空格、制表符、换行符）
4. 标识符和字面量的长度限制
5. 错误检测与恢复（跳过整个块）

标记类型

根据题目描述，FORCAL\texttt{FORCAL}FORCAL的标记包括：

注意：保留字（如begin、read等）在词法上被视为标识符，语义分析阶段再区分。

错误的类型

可能遇到的错误包括：

1. 无效字符（既不是标记字符，也不是空白，也不是注释开始）
2. 标识符长度超过323232
3. 字面量长度超过888
4. 字符:后面不跟=（即孤立的冒号）
5. 标识符全为数字（但长度符合字面量要求时，应识别为字面量而非标识符）

解题思路

步骤一：逐行处理

输入可能包含多个块，块之间以空行分隔。因此，需要逐行读取输入，遇到空行时表示当前块结束，输出一个空行并重置错误标志。

步骤二：注释处理

注释以--开头，到行尾结束。当遇到-且下一个字符也是-时，忽略该行剩余的所有内容。

步骤三：标记识别

使用一个状态机或简单的if-else结构逐个字符处理：

1. 单字符标记：(,),+,-,;,,

   • 直接输出该字符

2. 双字符标记：:=

   • 遇到:时，检查下一个字符是否为=
   • 如果是，输出:=并跳过两个字符
   • 如果不是，报错

3. 标识符/字面量

   • 遇到字母、数字或下划线时，开始收集
   • 收集直到遇到非标识符字符
   • 判断是标识符还是字面量：
     • 如果所有字符都是数字 → 字面量
     • 否则 → 标识符
   • 检查长度限制：
     • 标识符：长度 ≤323232
     • 字面量：长度 ≤888
   • 如果长度超限，报错

4. 空白字符

   • 空格、制表符：直接跳过

5. 无效字符

   • 其他任何字符都视为错误

步骤四：错误处理

一旦在某个块中检测到错误：

• 输出TOKEN ERROR
• 设置错误标志
• 跳过当前块的剩余行（直到遇到空行）

步骤五：输出格式

• 每个标记单独一行
• 标记与输入中的形式完全相同（保留原始大小写）
• 每个块结束后输出一个空行

算法复杂度分析

时间复杂度

• 遍历输入文件的每个字符：O(L)O(L)O(L)，其中LLL是输入文件的总长度
• 每个字符最多被处理一次

空间复杂度

• 只使用常数额外空间（存储当前行和临时标记字符串）
• 总空间复杂度：O(1)O(1)O(1)

正确性证明

引理 1：注释处理规则--到行尾是正确的。

证明：根据题目定义，注释以--开始，到行尾结束。当遇到-且下一个字符也是-时，剩余字符都不是标记，应被忽略。□\square□

引理 2：标识符/字面量的识别规则是正确的。

证明：

• 标识符和字面量都由字母、数字、下划线组成
• 区别在于是否包含非数字字符
• 如果全部是数字，则是字面量；否则是标识符
• 这与题目定义一致□\square□

引理 3：长度检查规则是正确的。

证明：

• 标识符长度 ≤323232（题目规定）
• 字面量长度 ≤888（最多888位数字）
• 超出长度限制的字符串不是有效的标记□\square□

引理 4：遇到错误后跳过整个块是正确的。

证明：题目规定遇到错误字符串后，输出TOKEN ERROR并继续处理下一个块。因此需要跳过当前块的所有剩余内容，直到遇到空行。□\square□

参考代码

// FORCAL// UVa ID: 309// Verdict: Accepted// Submission Date: 2016-11-10// UVa Run Time: 0.010s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);boolerror=false;// 当前块是否发生错误string line;while(getline(cin,line)){// 空行表示一个数据块的结束if(line.length()==0){cout<<'\n';// 输出块之间的空行error=false;// 重置错误标志continue;}// 如果当前块已经发生错误，跳过剩余行if(error)continue;intposition=0;while(position<line.length()){// 处理单字符标记：括号、加号、分号、逗号if(line[position]=='('||line[position]==')'||line[position]=='+'||line[position]==';'||line[position]==','){cout<<line[position]<<'\n';position++;}// 处理注释：以 -- 开头，忽略到行尾elseif(line[position]=='-'&&position+1<line.length()&&line[position+1]=='-'){break;// 跳过该行剩余部分}// 处理单字符减号运算符elseif(line[position]=='-'){cout<<line[position]<<'\n';position++;}// 处理赋值运算符 :=elseif(line[position]==':'){if(position+1<line.length()&&line[position+1]=='='){cout<<":="<<'\n';position+=2;}else{// 孤立的冒号：错误error=true;}}// 处理标识符或字面量elseif(isalpha(line[position])||isdigit(line[position])||line[position]=='_'){string block;boolall_are_digits=true;// 标记是否全为数字// 收集连续的标识符字符while(position<line.length()){if(isalpha(line[position])||isdigit(line[position])||line[position]=='_'){block+=line[position];if(all_are_digits)all_are_digits=isdigit(line[position]);// 只要有一个非数字，就不是字面量}else{break;}position++;}// 检查长度限制if((!all_are_digits&&block.length()>32)||(all_are_digits&&block.length()>8)){error=true;// 标识符超过32字符或字面量超过8位}else{cout<<block<<'\n';// 输出识别的标记}}// 处理空白字符：空格和制表符elseif(!isblank(line[position])){// 无效字符：既不是标记字符，也不是空白error=true;}else{// 空白字符，跳过position++;}// 如果发生错误，输出错误信息并跳出循环if(error){cout<<"TOKEN ERROR\n";break;}}}return0;}

总结

本题的核心在于：

1. 词法分析：识别标识符、字面量、运算符、分隔符
2. 注释处理：--到行尾
3. 长度限制：标识符 ≤323232，字面量 ≤888
4. 错误恢复：遇到错误后跳过整个块

关键点回顾

词法分析的一般步骤

1. 输入预处理（处理注释、空白）
2. 根据当前字符确定标记类型
3. 收集标记内容
4. 验证标记合法性（长度、格式）
5. 输出标记或错误信息

这种“逐字符扫描 + 状态判断”的解题模式，是词法分析器的典型实现方式。