题目描述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语法规范的标记并处理错误情况。核心挑战识别多种类型的标记标识符、字面量、运算符、分隔符处理注释--到行尾处理空白字符空格、制表符、换行符标识符和字面量的长度限制错误检测与恢复跳过整个块标记类型根据题目描述FORCAL\texttt{FORCAL}FORCAL的标记包括类型示例说明标识符A1,x_2,begin字母/数字/下划线至少一个非数字长度 ≤ 32字面量123,0,99999999纯数字字符串长度 ≤ 8赋值运算符:两个字符组成的单个标记运算符,-单字符运算符括号(,)单字符括号分隔符;,,单字符分隔符注意保留字如begin、read等在词法上被视为标识符语义分析阶段再区分。错误的类型可能遇到的错误包括无效字符既不是标记字符也不是空白也不是注释开始标识符长度超过323232字面量长度超过888字符:后面不跟即孤立的冒号标识符全为数字但长度符合字面量要求时应识别为字面量而非标识符解题思路步骤一逐行处理输入可能包含多个块块之间以空行分隔。因此需要逐行读取输入遇到空行时表示当前块结束输出一个空行并重置错误标志。步骤二注释处理注释以--开头到行尾结束。当遇到-且下一个字符也是-时忽略该行剩余的所有内容。步骤三标记识别使用一个状态机或简单的if-else结构逐个字符处理单字符标记(,),,-,;,,直接输出该字符双字符标记:遇到:时检查下一个字符是否为如果是输出:并跳过两个字符如果不是报错标识符/字面量遇到字母、数字或下划线时开始收集收集直到遇到非标识符字符判断是标识符还是字面量如果所有字符都是数字 → 字面量否则 → 标识符检查长度限制标识符长度 ≤323232字面量长度 ≤888如果长度超限报错空白字符空格、制表符直接跳过无效字符其他任何字符都视为错误步骤四错误处理一旦在某个块中检测到错误输出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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);boolerrorfalse;// 当前块是否发生错误string line;while(getline(cin,line)){// 空行表示一个数据块的结束if(line.length()0){cout\n;// 输出块之间的空行errorfalse;// 重置错误标志continue;}// 如果当前块已经发生错误跳过剩余行if(error)continue;intposition0;while(positionline.length()){// 处理单字符标记括号、加号、分号、逗号if(line[position](||line[position])||line[position]||line[position];||line[position],){coutline[position]\n;position;}// 处理注释以 -- 开头忽略到行尾elseif(line[position]-position1line.length()line[position1]-){break;// 跳过该行剩余部分}// 处理单字符减号运算符elseif(line[position]-){coutline[position]\n;position;}// 处理赋值运算符 :elseif(line[position]:){if(position1line.length()line[position1]){cout:\n;position2;}else{// 孤立的冒号错误errortrue;}}// 处理标识符或字面量elseif(isalpha(line[position])||isdigit(line[position])||line[position]_){string block;boolall_are_digitstrue;// 标记是否全为数字// 收集连续的标识符字符while(positionline.length()){if(isalpha(line[position])||isdigit(line[position])||line[position]_){blockline[position];if(all_are_digits)all_are_digitsisdigit(line[position]);// 只要有一个非数字就不是字面量}else{break;}position;}// 检查长度限制if((!all_are_digitsblock.length()32)||(all_are_digitsblock.length()8)){errortrue;// 标识符超过32字符或字面量超过8位}else{coutblock\n;// 输出识别的标记}}// 处理空白字符空格和制表符elseif(!isblank(line[position])){// 无效字符既不是标记字符也不是空白errortrue;}else{// 空白字符跳过position;}// 如果发生错误输出错误信息并跳出循环if(error){coutTOKEN ERROR\n;break;}}}return0;}总结本题的核心在于词法分析识别标识符、字面量、运算符、分隔符注释处理--到行尾长度限制标识符 ≤323232字面量 ≤888错误恢复遇到错误后跳过整个块关键点回顾知识点说明标记类型标识符、字面量、运算符、分隔符标识符规则字母/数字/下划线至少一个非数字长度 ≤ 32字面量规则纯数字长度 ≤ 8注释--到行尾空白字符空格、制表符、换行符赋值运算符:是单个标记错误处理输出TOKEN ERROR跳过当前块词法分析的一般步骤输入预处理处理注释、空白根据当前字符确定标记类型收集标记内容验证标记合法性长度、格式输出标记或错误信息这种“逐字符扫描 状态判断”的解题模式是词法分析器的典型实现方式。
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语法规范的标记并处理错误情况。核心挑战识别多种类型的标记标识符、字面量、运算符、分隔符处理注释--到行尾处理空白字符空格、制表符、换行符标识符和字面量的长度限制错误检测与恢复跳过整个块标记类型根据题目描述FORCAL\texttt{FORCAL}FORCAL的标记包括类型示例说明标识符A1,x_2,begin字母/数字/下划线至少一个非数字长度 ≤ 32字面量123,0,99999999纯数字字符串长度 ≤ 8赋值运算符:两个字符组成的单个标记运算符,-单字符运算符括号(,)单字符括号分隔符;,,单字符分隔符注意保留字如begin、read等在词法上被视为标识符语义分析阶段再区分。错误的类型可能遇到的错误包括无效字符既不是标记字符也不是空白也不是注释开始标识符长度超过323232字面量长度超过888字符:后面不跟即孤立的冒号标识符全为数字但长度符合字面量要求时应识别为字面量而非标识符解题思路步骤一逐行处理输入可能包含多个块块之间以空行分隔。因此需要逐行读取输入遇到空行时表示当前块结束输出一个空行并重置错误标志。步骤二注释处理注释以--开头到行尾结束。当遇到-且下一个字符也是-时忽略该行剩余的所有内容。步骤三标记识别使用一个状态机或简单的if-else结构逐个字符处理单字符标记(,),,-,;,,直接输出该字符双字符标记:遇到:时检查下一个字符是否为如果是输出:并跳过两个字符如果不是报错标识符/字面量遇到字母、数字或下划线时开始收集收集直到遇到非标识符字符判断是标识符还是字面量如果所有字符都是数字 → 字面量否则 → 标识符检查长度限制标识符长度 ≤323232字面量长度 ≤888如果长度超限报错空白字符空格、制表符直接跳过无效字符其他任何字符都视为错误步骤四错误处理一旦在某个块中检测到错误输出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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);boolerrorfalse;// 当前块是否发生错误string line;while(getline(cin,line)){// 空行表示一个数据块的结束if(line.length()0){cout\n;// 输出块之间的空行errorfalse;// 重置错误标志continue;}// 如果当前块已经发生错误跳过剩余行if(error)continue;intposition0;while(positionline.length()){// 处理单字符标记括号、加号、分号、逗号if(line[position](||line[position])||line[position]||line[position];||line[position],){coutline[position]\n;position;}// 处理注释以 -- 开头忽略到行尾elseif(line[position]-position1line.length()line[position1]-){break;// 跳过该行剩余部分}// 处理单字符减号运算符elseif(line[position]-){coutline[position]\n;position;}// 处理赋值运算符 :elseif(line[position]:){if(position1line.length()line[position1]){cout:\n;position2;}else{// 孤立的冒号错误errortrue;}}// 处理标识符或字面量elseif(isalpha(line[position])||isdigit(line[position])||line[position]_){string block;boolall_are_digitstrue;// 标记是否全为数字// 收集连续的标识符字符while(positionline.length()){if(isalpha(line[position])||isdigit(line[position])||line[position]_){blockline[position];if(all_are_digits)all_are_digitsisdigit(line[position]);// 只要有一个非数字就不是字面量}else{break;}position;}// 检查长度限制if((!all_are_digitsblock.length()32)||(all_are_digitsblock.length()8)){errortrue;// 标识符超过32字符或字面量超过8位}else{coutblock\n;// 输出识别的标记}}// 处理空白字符空格和制表符elseif(!isblank(line[position])){// 无效字符既不是标记字符也不是空白errortrue;}else{// 空白字符跳过position;}// 如果发生错误输出错误信息并跳出循环if(error){coutTOKEN ERROR\n;break;}}}return0;}总结本题的核心在于词法分析识别标识符、字面量、运算符、分隔符注释处理--到行尾长度限制标识符 ≤323232字面量 ≤888错误恢复遇到错误后跳过整个块关键点回顾知识点说明标记类型标识符、字面量、运算符、分隔符标识符规则字母/数字/下划线至少一个非数字长度 ≤ 32字面量规则纯数字长度 ≤ 8注释--到行尾空白字符空格、制表符、换行符赋值运算符:是单个标记错误处理输出TOKEN ERROR跳过当前块词法分析的一般步骤输入预处理处理注释、空白根据当前字符确定标记类型收集标记内容验证标记合法性长度、格式输出标记或错误信息这种“逐字符扫描 状态判断”的解题模式是词法分析器的典型实现方式。
