高等教育：《词法分析(2)》

自然语言处理的词法分析与句法分析自然语言处理是人工智能领域的一个重要分支，旨在使计算机能够理解和处理人类语言。

其中，词法分析和句法分析是自然语言处理的两个主要任务。

词法分析负责将一段文本分解成单词或词素，而句法分析则对文本的语法结构进行分析和解析。

本文将详细介绍词法分析和句法分析的基本概念、方法和应用。

一、词法分析1. 概念和任务词法分析是自然语言处理中的一个基础任务，主要目标是将一段文本拆分成一个个单词或词素。

词法分析可以看作是自然语言处理中最初的处理环节，在很大程度上决定了后续处理任务的难度和准确性。

具体而言，词法分析的任务包括以下几个方面：（1）分词：将连续的文本流分成一个个独立的单词。

分词在汉语处理中尤为重要，因为汉语中没有像英语中的空格来明确标识词之间的边界。

（2）词性标注：对每个单词进行词性标注，即确定它的词性类别（如名词、动词、形容词等）。

词性标注常常需要结合上下文语境进行判断。

（3）词干提取：将一个单词的派生形式还原为它的词干或原型形式。

例如，“running”和“ran”都可以还原为“run”。

2. 方法和技术（1）规则法：基于规则的词法分析方法依靠人工定义的词法规则和规则库进行分析。

这种方法简单直观，易于理解和实现，但对规则的编写需要大量的人工劳动，并且规则难以适应复杂多变的语言现象。

（2）统计法：统计法通过学习大量的语料库数据，利用统计模型来进行词法分析。

常见的统计模型包括隐马尔可夫模型（Hidden Markov Model，HMM）、最大熵模型（Maximum Entropy Model，MEM）、条件随机场（Conditional Random Field，CRF）等。

统计法的优点是能够自动学习语言规律，适应性较好，但需要大量的训练数据和计算资源。

（3）深度学习法：深度学习方法基于神经网络，通过多层的神经网络结构来进行词法分析。

典型的深度学习模型包括循环神经网络（Recurrent Neural Network，RNN）、长短期记忆网络（Long Short-Term Memory，LSTM）等。

实验2 词法分析（4学时）实验要求：1. TEST语言的单词符号有：标识符：字母打头，后接字母数字,识别出的标识符用ID标记。

保留字（它是标识符的子集）：if,else,for,while,do,int,write,read，识别出的保留字直接用该保留字标记。

无符号整数：由数字组成，用NUM标记。

分界符：+、-、*、/、（、）、；、，>、<、{、}、!等单分界符，直接用单分界符标记。

>=、<=、!=、==等双字符分界符，直接用双分界符标记。

注释符：用/*….*/括起为了从源程序字符流中正确识别出各类单词符号，相邻的标识符、整数或保留字之间至少要用一个空格分开。

TEST语言的各类单词符号的正则文法规则如下：<ID>∷=<letter>|ID<letter>|ID<digit><NUM>∷=<digit>|NUM <digit><letter>∷= a|b|…|z|A|B|…|Z<digit>∷=1|2|…|9|0<singleword>∷=+|-|*|/|=|（|）|{|}|：|，|；|＜|＞|!<doubleword>∷=＞=|＜=|！=|==<commend_first>∷=/*<commend_last>∷=*/2、修改TESTscan（）程序，添加其余符号的处理。

1、AAA.test内容：= + - * / < > ( ) [ ] { } ; : ' " , == >= <= !=if else for while do int read write 358 aaa输出BBB.test的内容为：if else for while do int read write 358 aaaif else for while do int read write NUM ID这部分实验要求同学理解单词符号。

作业第二题：（上海交通大学1984年考研试题）下述正规表达式中（1）与（a*|b）*(c|d)等价。

⑴(a|b)*c|(a|b)*d⑵a*(c|d)|b*(c|d)⑶a*(c|d)*|b(c|d)*第三题：（西北工业大学1999年考研试题）设字母表∑={a,b,0,1}，请写出满足下述条件的正则表达式：以字母a或b打头，以1结尾。

答案：a(a|b|0|1)*1| b(a|b|0|1)*1第四题：(1)构造一个正规式，它接受∑={a，b}上所有包含ab的字符串。

(2)构造一个正规式，它接受∑={a，b}上所有以ab结尾字符串。

(3)构造一个正规式，它接受∑={a，b,c}上符合以下规则的字符串：如果以a开头，则串内至少包含一个c；如果以b开头，则串内至多包含一个 a。

答案：(1) (a|b) * ab (a|b)*(2) (a|b) * ab(3) a (a|b|c)* c (a|b|c)* | b ( (b|c) * a(b|c) * | (b|c) * )第六题：试构造正规表达式((a*|b)(b*a)) *的NFA，然后确定化和最小化。

答案：与正规表达式等价的NFA如下所示：注：未标明转移条件的，均默认为条件为ε上图对应状态名Si如下：3 4 5 61 2 9 10 11 12 13 14 15 167 8S1闭包={ S1，S2，S3，S4，S6，S7，S9，S10，S11，S13，S14，S16 } S2闭包={ S2，S3，S4，S6，S7，S9，S10，S11，S13，S14 }S3闭包={ S3，S4，S6，S9，S10，S11，S13，S14 }S4闭包={ S4 }S5闭包={ S4，S5，S6，S9，S10，S11，S13，S14 }S6闭包={ S6，S9，S10，S11，S13，S14 }S7闭包={ S7 }S8闭包={ S8，S9，S10，S11，S13，S14 }S9闭包={ S9，S10，S11，S13，S14 }S10闭包={ S10，S11，S13，S14 }S11闭包={ S11 }S12闭包={ S11，S12 ，S13，S14}S13闭包={ S13，S14 }S14闭包={ S14 }S15闭包={ S2，S3，S4，S6，S7，S9，S10，S11，S13，S14，S15，S16 }S16闭包={ S16 }DFA取Q1= S1闭包={ S1，S2，S3，S4，S6，S7，S9，S10，S11，S13，S14，S16 } 则f(Q1,a)= S5闭包+ S15闭包={ S2，S3，S4，S5，S6，S7，S9，S10，S11，S13，S14，S15，S16 }=Q2f(Q1,b)= S8闭包+ S12闭包={ S8，S9，S10，S11，S12，S13，S14 }=Q3此时，Q2，Q3未标记。

北京大学信息科学技术学院2015年春季学期《编译技术》第3章词法分析（2）Lexical Analysis【对应教材 3.3- 3.5】取下一个Token符号表语法分析器词法分析器上节内容回顾☐词法分析器的作用Token(词法单元)源程序☐词法单元的描述方法⏹ 字母表、符号串和语言⏹正则集合、正则表达式和正则定义Review Questions☐写一个正则表达式，表示所有能被5整除的十进制数。

☐写一个正则表达式，表示所有能被5整除的不包含前导0的十进制数。

☐写一个正则表达式，表示所有能被5整除的二进制数。

☐词法分析器的作用☐词法单元的规约⏹串和语言；正则表达式、正则定义☐词法单元的识别☐词法分析器生成工具—LEX☐有限自动机(Finite Automata)☐正则表达式到有限自动机☐词法分析器生成工具的设计☐一般有两种方式：⏹借助状态转换图（有限自动机的图形表示）手工构造词法分析器。

⏹通过LEX自动生成词法分析器。

正则表达式⇒ NFA⇒ DFA⇒ minDFA⇒词法分析器☐状态转换图(transition diagram)⏹状态(state)：表示在识别词素时可能出现的情况状态看作是已处理部分的总结某些状态为接受状态或最终状态，表明已找到词素加上*的接受状态表示最后读入的符号不在词素中 ☐开始状态（初始状态）：用“开始”边表示⏹边(edge)：从一个状态指向另一个状态；边的标号是一个或多个符号当前符号为s，下一个输入符号为a，就沿着从s离开,标号为a的边到达下一个状态= 2r 1> 3<other *开始40 =>5 return(relop, EQ)= other 768 *eturn(relop, LE) return(relop, NE) return(relop, LT)return(relop, GE) return(relop, GT)letter或digit开始letter other *11 return(getToken(), installId( ))9 10number → digit+ (.digit+)? (E (+ | -)? digit+)?digit Edigitdigitdigit开始12 digit13.14digit15E+/-16digit17 18other other other*19开始20delim21other*22delimdelim → blank | tab | newline ws → delim +北京大学信息科学技术学院手动编写词法分析程序：以relop 为例TOKEN getRelop ( ){ TOKEN retToken = new ( RELOP ) ;while ( 1 ) { /* 反复读入字符，直到return 或 遇到错误 */switch (state) {case 0 : c = nextChar ( ) ;if ( c == ' < ' ) state = 1 ; else if ( c == ' = ' ) state = 5 ; else if ( c == ' > ' ) state = 6 ; else fail ( ) ; /* 非关系算符 */ break ;case 1 : …… …… 2 =return(relop, LE) case 8 : retract ( ); retToken.attribute = GT; return (retToken); 开始1> < other3 return(relop, NE)4 * return(relop, LT)} 0= } >5 return(relop, EQ)} 2015年春季学期 《编译技术》课程= 6 other 7 return(relop, GE)8* return(relop 1, G 1T)首先通过正则表达式来描述词法单元的模式 基本目标：判断一个串s是否属于一个正则表达式R表示的语言s∈L(R)在现实中，还要能够连续识别多个不同类别的词法单元if (a == b) …(1)分别为每一类词法单元写出正则表达式R i(2)构造一个正则表达式R来匹配所有的词法单元R = R1 | R2 | … | R k(3)设输入为x1x2…x n, 对1≤i≤n，检查是否x1…x i∈L(R)(4)如果匹配成功，则存在j，使得x1…x i∈L(R j)(5)把x1…x i从输入中移走，继续执行（3）如何确定匹配的长度？有可能多个前缀都可以产生匹配解决办法：匹配最长可能的串选择哪个正则表达式来匹配？有可能多个正则表达式都可以匹配解决办法：排在前面的正则表达式优先匹配如果所有正则表达式都不能匹配怎么办？怎么报错？解决办法：可以构造一个ERROR正则表达式，放到所有表达式在后面，用来报告错误信息14Quiz：选择题使用如下的词法描述，在识别字符串“dictatorial” 的过程中会如何进行分割？dict (1)dictator (2)[a-z]* (3)dictatorial (4)a)4b)3c) 1, 3d) 2, 3内容提要词法分析器的作用词法单元的规约串和语言；正则表达式、正则定义 词法单元的识别☐词法分析器生成工具—LEX 有限自动机(Finite Automata)正则表达式到有限自动机词法分析器生成工具的设计Lex 简介Lex 是一种词法分析程序的自动构造工具。