ILD

bison学习笔记1:concepts
作者:Yuan Jianpeng 邮箱:yuanjp89@163.com
发布时间:2019-8-4 站点:Inside Linux Development

1 The Concepts of Bison

所有的context-free language都可以用BNF表达,所有用BNF表达的语言都可以有bison解析。


1.2 From Formal Rules to Bison Input

nonterminal symbol,在bison中是一个identifier,用小写表示。

terminal symbol,也被叫做token type,通常用大写。


例子

stmt: RETURN expr ’;’ ;


1.3 Semantic Values

如果一个rule提到了叫interger const的terminal symbol,那么意味着任何整数常量都是语法上合法的。x+4和x+1在语法上是等价的。


但是精确的值有是非常重要的。因此,bison中的每个token都有token type和semantic value。


token type是grammar中定义的terminal symbol,例如INTEGER,IDENTIFIER,或者','。token type决定了所有的东西:它可以出现在哪里,它和其它token如何组合。grammar rule只知道token的类型,不知道token的其它任何东西。


semantic value包含一个token除了type之外的所有信息,如一个整数的值,一个标识符的名字。


每个grouping也可以有semantic value,比如表达式有一个值。


1.4 Semantic Actions

一个grammar rule可以有一个action,由c语句组成。每次parser识别一个rule,action都被执行。


大多数时间,action的目的是计算整个结构的semantic value。


例如:

expr: expr ’+’ expr    { $$ = $1 + $3; } ;


1.5 Writing GLR Parsers

有时需要提前读取下一个token,才能确定rule的匹配。


如果你在bison declarations包含 %glr-parser,结果是一个Generalized LR (GLR) parser。


1.6 locations

每个token有关联的位置。用@$,@1等表示。


1.7 Bison Ouput: the parser Implementation File

bison的输出一个是实现parser的C源码文件。这个parser叫做bison parser。源文件叫做bison parser implementation file。


1.8 Stages in Using Bison

使用bison设计真实的语言的步骤:

1 指定bison认识的语法

2 写一个lexical analyzer来处理输入,并产生tokens

3 写一个控制函数来调用bison产生的parser。

4 写一个error-reporting routines


最终编译的过程:

5 执行bison来产生parser。

6 编译bison的输出,已经其它源码文件

7 链接目标文件成一个最终的输出。


1.9 The overall layout of a bison grammar

bison语法文件的通用格式如下:

1
2
3
4
5
6
7
8
9
10
%{
Prologue
%}
 
Bison declarations
 
%%
Grammar rules
%%
Epilogue


%% %{ %}用来分开sections。


prologue是c语言代码,用来定义action用到类型,定义变量。可以使用预处理,可以使用#include。声明lexical analyzer的接口yylex,以及error printer接口yyerror等。


bison declarations用来声明terminal和nonterminal symbol的名字。描述运算符的优先级,各种符号的semantic values的数据类型。


grammar rules定义了如何构造nonterminal symbol,


epilogue用来包含你想要的任何代码。


Copyright © linuxdev.cc 2017-2024. Some Rights Reserved.