• 自上而下解析器与自下而上解析器

    两种基本类型的解析器
    服务器君一共花费 7.531 ms 进行了 3 次数据库查询,努力地为您提供了这个页面。
    广告很萌的

    两种基本类型的解析器

    有两种基本类型的解析器:自上而下解析器和自下而上解析器。比如我们之前在 词法语法分析在浏览器中的作用 提到的,Webkit就是使用自底向上的解析器,而Gecko使用自顶向下的解析器。

    直观地来说,自上而下的解析器从语法的高层结构出发,尝试从中找到匹配的结构。而自下而上的解析器从低层规则出发,将输入内容逐步转化为语法规则,直至满足高层规则。

    让我们来看看这两种解析器会如何解析我们的示例:

    自上而下的解析器会从高层的规则开始:首先将2 + 3标识为一个表达式,然后将 2 + 3 - 1 标识为一个表达式(标识表达式的过程涉及到匹配其他规则,但是起点是最高级别的规则)。

    自下而上的解析器将扫描输入内容,找到匹配的规则后,将匹配的输入内容替换成规则。如此继续替换,直到输入内容的结尾。部分匹配的表达式保存在解析器的堆栈中。

    堆栈输入
     2 + 3 - 1
    + 3 - 1
    项运算3 - 1
    表达式- 1
    表达式运算符1
    表达式 

    这种自下而上的解析器称为移位归约解析器,因为输入在向右移位(设想有一个指针从输入内容的开头移动到结尾),并且逐渐归约到语法规则上。

    自动生成解析器

    有一些工具可以帮助您生成解析器,它们称为解析器生成器。您只要向其提供您所用语言的语法(词汇和语法规则),它就会生成相应的解析器。创建解析器需要对解析有深刻理解,而人工创建优化的解析器并不是一件容易的事情,所以解析器生成器是非常实用的。

    Webkit 使用了两种非常有名的解析器生成器:用于创建词法分析器的 Flex 以及用于创建解析器的 Bison(您也可能遇到 Lex 和 Yacc 这样的别名)。Flex 的输入是包含标记的正则表达式定义的文件。Bison 的输入是采用 BNF 格式的语言语法规则。

    Webkit CSS 解析器

    Webkit 使用 Flex 和 Bison 解析器生成器,通过 CSS 语法文件自动创建解析器。正如我们之前在解析器简介中所说,Bison 会创建自下而上的移位归约解析器。

    Firefox 使用的是人工编写的自上而下的解析器。这两种解析器都会将 CSS 文件解析成 StyleSheet 对象,且每个对象都包含 CSS 规则。CSS 规则对象则包含选择器和声明对象,以及其他与 CSS 语法对应的对象。

    解析 CSS

    PS:词汇和语法的正式定义

    词汇通常用正则表达式表示。

    例如,我们的示例语言可以定义如下:

    INTEGER :0|[1-9][0-9]*
    PLUS : +
    MINUS: -
    

    正如您所看到的,这里用正则表达式给出了整数的定义。

    语法通常使用一种称为 BNF 的格式来定义。我们的示例语言可以定义如下:

    expression :=  term  operation  term
    operation :=  PLUS | MINUS
    term := INTEGER | expression
    

    之前我们说过,如果语言的语法是与上下文无关的语法,就可以由常规解析器进行解析。与上下文无关的语法的直观定义就是可以完全用 BNF 格式表达的语法。有关正式定义,请参阅关于与上下文无关的语法的维基百科文章

更多 推荐条目

Welcome to NowaMagic Academy!

现代魔法 推荐于 2013-02-27 10:23   

本章最新发布
随机专题
  1. [PHP程序设计] PHP与Stream流 5 个条目
  2. [移动开发] Android View注入框架Butter Knife 3 个条目
  3. [软件工程与项目管理] 浏览器与CSS渲染技巧 2 个条目
  4. [计算机算法] 两数交换的各种算法细节 2 个条目
  5. [Linux操作系统] 基本 Linux Shell 命令 2 个条目
  6. [数据库技术] 数据库范式篇 5 个条目
  7. [智力开发与知识管理] 超越整体性学习 5 个条目
  8. [移动开发] Android 网络通信框架Volley 1 个条目
  9. [PHP程序设计] 声明式编程范式 12 个条目
  10. [PHP程序设计] PHP里的布尔类型 3 个条目
  11. [计算机算法] TAOCP与算法 12 个条目
  12. [数据结构] 散列表(哈希表) 13 个条目
窗口 -- [博客]