【现代编译器】语法分析——正则表达式,上下文无关文法,递归下
1 正则表达式1 最基础:
使用正则表达式的最简单途径——String类的内建功能:
如果正则表达式不是只使用一次的话,非String对象的正则表达式明显具备更佳的性能。这个在稍后就会看到。
例:下面的每一个正则表达式都能成功匹配字符序列“Rudolph” for(String pattern: new String[]{ "Rudolph","[rR]udolph","[rR][aeiou][a-z].*","R.*" }) }) System.out.println("Rudolph".matched(pattern)); 2 量词量词描述了一个模式吸收输入文本的方式
测试代码:
import java.util.regex.*; public class testRegex { public static String t = "Java now has regular expressions"; public static String r = "((^[aeious])|(s+[aeiou]))" { System.out.println("Input: "" + args[0] + """); for(String arg: args) { System.out.println("Regular expression: "" + arg + """); Pattern p = Pattern.compile(arg); Matcher m = p.matcher(t); while(m.find()) { System.out.println("Match "" + m.group() + "" at position" + m.start() + "-" + (m.end()-1)); } } } }
功能更强大的正则表达式工具:
2 正题——语法分析
简单的看了一下Java中正则表达式的基本知识,下面仔细看一看在虎书中语法分析的章节。
2.1 词法分析器实现正则表达式
匹配括号对于有限自动机是不可识别的。
在翻译成有限自动机以前,在所有正则表达式出现digits的地方都简单地用右边的式子代替。
简化的概念并没有增前正则表达式的描述能力,除非简化形式是递归的。这种递归附加功能正式在语法分析中所需要的,一旦使用了递归简化形式,就不再需要进行迭代,除非是表达式的首部。
定义:
expr = ab(c|d)e可以用附加定义重写: aux = c d expr = a b aux e 为了避免使用交替符号,对于同一符号,可以使用一些辅助扩充: aux = c aux = d expr = a b aux e 另外一个i例子: expr = (a b c)*
重写为:
expr = (a b c)expr expr = & 2.2 上下文无关文法CFG
CFG = <T,N,P,S>
T:终结符 N:非终结符 P:产生式集合 S:初始非终结符
正如正则表达式可以静态声明的方式定义词法结构一样,文法也可以用声明的方式定义语法结构,但需要比有限自动机更强大的方式来分析文法描述的语言。
对于语法分析,字符串就是源程序,符号就是词法记号,字母表就是词法分析器返回的记号类型集。
文法的产生式集: symbol -> symbol symbol ... symbol
有0个或多于0个的记号在产生式的右边,这些符号要么是终结符,即描述语言中字符串在字母表中的记号;要么是非终结符,即出现在产生式左边的记号。产生式左边不会出现终结符的记号。最后,还需要使用一个非终结符作为文法的开始符号。
推导:从开始符号出发,对于任一非终结符,用其产生式的右侧部分进行替换并重复进行这一操作。 2.3 分析树
分析树就是将推导式中的每个符号同其派生符号连接而成。
二义性文法:若一个文法可以用两棵不同的分析树派生出同一个句子,那么该文法就是二义性的。
如何避免二义性,即如何将二义性文法转换成非二义性文法:
途径:引入一些非终结符号可以得到非二义性文法:
文法3.5为二义性文法:
引入T和F后所得的非二义性文法:
符号E T 和F分别代表表达式、项和因子。习惯上,因子用于乘法,项用于加法。
综上,消除二义性的通常做法是转换文法,虽然这些文法只是在文法上存在二义性,但是它们在编程时也会出现二义性。
通常,使用$符号代表全文的结束,即分析器读入的终结符。
文法3.8加入终结符后的文法:
2.4 预测分析——递归下降分析
把每个文法产生式转换成一个递归函数的子句。
递归下降分析器对应每个非终结符都有一个函数,对应每个产生式都有一个子句。
递归下降、预测或者分析仅限于如下的文法中:每个子表达式的第一个终结符号为选择产生式提供了足够多的信息。这样们需要引入一个FIRST集的概念才能推导出一个无冲突递归下降分析器。
PS: 虎书太难懂了,今天就先到这吧。。
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- 初次尝试使用typescript开发react-native
- Swift3.0--GCD
- c# – 将FlowDocument作为XPS文档保存到磁盘
- ruby-on-rails – Ruby on rails 3:link_to:remote => tr
- ios – “架构x86_64的未定义符号:”Branch.io出错
- 字符串中的Sqlite绑定文字
- c# – 需要帮助理解Microsoft对File.ReadLines和File.ReadA
- ruby-on-rails – 如何在ActiveAdmin上翻译模块内的模型?
- Flash shader滤镜的使用
- <oracle.adf.view> <SimpleSelectOneRende