flex 與 bison

前言

Flex and bison are tools designed for writers of compilers and interpreters, althoughthey are also useful for many applications that will interest noncompiler writers. Anyapplication that looks for patterns in its input or has an input or command language isa good candidate for flex and bison. Furthermore, they allow for rapid applicationprototyping, easy modification, and simple maintenance of programs. To stimulateyour imagination, here are a few things people have used flex and bison, or their predecessors lex and yacc, to develop:The desktop calculator bcThe tools eqn and pic, typesetting preprocessors for mathematical equations and complex picturesMany other "domain-specific languages" targeted for a particular application PCC, the Portable C Compiler used with many Unix systemsFlex itselfA SQL database language translatorScope of This BookChapter 1, Introducing Flex and Bison, gives an overview of how and why flex and bisonare used to create compilers and interpreters and demonstrates some simple applica-tions including a calculator built in flex and bison. It also introduces basic terms weuse throughout the book.Chapter 2, Using Flex, describes how to use flex. It develops flex applications that countwords in files, handle multiple and nested input files, and compute statistics on Cprograms.Chapter 3, Using Bison, gives a full example using flex and bison to develop a fullyfunctional desktop calculator with variables, procedures, loops, and conditional expressions. It shows the use of abstract syntax trees fASTs）, powerful and easy-to-usedata structures for representing parsed input.Chapter 4, Parsing SQL, develops a parser for the MySQL dialect of the SQL relationaldatabase language.

內(nèi)容概要

《flex 與 bison(影印版)》內(nèi)容簡介：如果你需要分析或處理Linux或Unix中的文本數(shù)據(jù)，這本有用的書籍就向你講解了如何使用flex和bison迅速解決問題?！秄lex與bison》被期待已久，是經(jīng)典O’Reilly系列書籍《lex & yacc》的續(xù)篇。在原書出版以來的近20年中，flex和bison已被證明比原來的Unix工具更可靠、更強(qiáng)大。《flex與bison》一書涵蓋了Linux和Unix程序開發(fā)中相同的重要核心功能，以及一些重要的新主題。你會找到適用于新手的修訂教程和適用于高級用戶的參考資料，以及對每個程序的基本用法的解釋，并且運(yùn)用它們創(chuàng)建簡單、獨(dú)立的應(yīng)用程序。有了《flex與bison》，你會發(fā)現(xiàn)這些靈活的工具提供的廣泛用途。包括的主題有：· 正則表達(dá)式工具無法處理的地址語法擠壓(address syrltax crunching)· 生成編譯器和解釋器，并運(yùn)用大范圍的文本處理功能· 解釋代碼、配置文件或任何其他結(jié)構(gòu)化的格式· 學(xué)習(xí)關(guān)鍵編程技術(shù)，包括抽象語法樹和符號表· 用完整的示例代碼實現(xiàn)一個完善的SQI一語法· 使用新的功能，如純(可重入)詞法分析器(Iexer)和語法分析器(parser)、功能強(qiáng)大的JGLR分析器和C++的接口

作者簡介

John Levine, Taughannock Networks的創(chuàng)始人，著有20余本技術(shù)書籍，其中包括《lex & yacc》和《qmail》，均為O’Reilly出版。

書籍目錄

Preface 1. Introducing Flex and Bison Lexical Analysis and Parsing Regular Expressions and Scanning Our First Flex Program Programs in Plain Flex Putting Flex and Bison Together The Scanner as Coroutine Tokens and Values Grammars and Parsing BNF Grammars Bison’s Rule Input Language Compiling Flex and Bison Programs Together Ambiguous Grammars: Not Quite Adding a Few More Rules Flex and Bison vs. Handwritten Scanners and Parsers Exercises 2. Using Flex Regular Expressions Regular Expression Examples How Flex Handles Ambiguous Patterns Context-Dependent Tokens File I/O in Flex Scanners Reading Several Files The I/O Structure of a Flex Scanner Input to a Flex Scanner Flex Scanner Output Start States and Nested Input Files Symbol Tables and a Concordance Generator Managing Symbol Tables Using a Symbol Table C Language Cross-Reference Exercises 3. Using Bison How a Bison Parser Matches Its Input Shift/Reduce Parsing What Bison’s LALR(1) Parser Cannot Parse A Bison Parser Abstract Syntax Trees An Improved Calculator That Creates ASTs Literal Character Tokens Building the AST Calculator Shift/Reduce Conflicts and Operator Precedence When Not to Use Precedence Rules An Advanced Calculator Advanced Calculator Parser Calculator Statement Syntax Calculator Expression Syntax Top-Level Calculator Grammar Basic Parser Error Recovery The Advanced Calculator Lexer Reserved Words Building and Interpreting ASTs Evaluating Functions in the Calculator User-Defined Functions Using the Advanced Calculator Exercises 4. Parsing SQL A Quick Overview of SQL Relational Databases Manipulating Relations Three Ways to Use SQL SQL to RPN The Lexer Scanning SQL Keywords Scanning Numbers Scanning Operators and Punctuation Scanning Functions and Names Comments and Miscellany The Parser The Top-Level Parsing Rules SQL Expressions Select Statements Delete Statement Insert and Replace Statements Update Statement Create Database Create Table User Variables The Parser Routines The Makefile for the SQL Parser Exercises 5. A Reference for Flex Specifications Structure of a Flex Specification Definition Section Rules Section User Subroutines BEGIN C++ Scanners Context Sensitivity Left Context Right Context Definitions (Substitutions) ECHO Input Management Stdio File Chaining Input Buffers Input from Strings File Nesting input() YY_INPUT Flex Library Interactive and Batch Scanners Line Numbers and yylineno Literal Block Multiple Lexers in One Program Combined Lexers Multiple Lexers Options When Building a Scanner Portability of Flex Lexers Porting Generated C Lexers Reentrant Scanners Extra Data for Reentrant Scanners Access to Reentrant Scanner Data Reentrant Scanners, Nested Files, and Multiple Scanners Using Reentrant Scanners with Bison Regular Expression Syntax Metacharacters REJECT Returning Values from yylex() Start States unput() yyinput() yyunput() yyleng yyless() yylex() and YY_DECL yymore() yyrestart() yy_scan_string and yy_scan_buffer YY_USER_ACTION yywrap() 6. A Reference for Bison Specifications Structure of a Bison Grammar Symbols Definition Section Rules Section User Subroutines Section Actions Embedded Actions Symbol Types for Embedded Actions Ambiguity and Conflicts Types of Conflicts Shift/Reduce Conflicts Reduce/Reduce Conflicts %expect GLR Parsers Bugs in Bison Programs Infinite Recursion Interchanging Precedence Embedded Actions C++ Parsers %code Blocks End Marker Error Token and Error Recovery %destructor Inherited Attributes ($0) Symbol Types for Inherited Attributes %initial-action Lexical Feedback Literal Block Literal Tokens Locations %parse-param Portability of Bison Parsers Porting Bison Grammars Porting Generated C Parsers Libraries Character Codes Precedence and Associativity Declarations Precedence Associativity Precedence Declarations Using Precedence and Associativity to Resolve Conflicts Typical Uses of Precedence Recursive Rules Left and Right Recursion Rules Special Characters %start Declaration Symbol Values Declaring Symbol Types Explicit Symbol Types Tokens Token Numbers Token Values %type Declaration %union Declaration Variant and Multiple Grammars Combined Parsers Multiple Parsers Using %name-prefix or the -p Flag Lexers for Multiple Parsers Pure Parsers y.output Files Bison Library main() yyerror() YYABORT YYACCEPT YYBACKUP yyclearin yydebug and YYDEBUG YYDEBUG yydebug yyerrok YYERROR yyerror() yyparse() YYRECOVERING() 7. Ambiguities and Conflicts The Pointer Model and Conflicts Kinds of Conflicts Parser States Contents of name.output Reduce/Reduce Conflicts Shift/Reduce Conflicts Review of Conflicts in name.output Common Examples of Conflicts Expression Grammars IF/THEN/ELSE Nested List Grammar How Do You Fix the Conflict? IF/THEN/ELSE (Shift/Reduce) Loop Within a Loop (Shift/Reduce) Expression Precedence (Shift/Reduce) Limited Lookahead (Shift/Reduce or Reduce/Reduce) Overlap of Alternatives (Reduce/Reduce) Summary Exercises 8. Error Reporting and Recovery Error Reporting Locations Adding Locations to the Parser Adding Locations to the Lexer More Sophisticated Locations with Filenames Error Recovery Bison Error Recovery Freeing Discarded Symbols Error Recovery in Interactive Parsers Where to Put Error Tokens Compiler Error Recovery Exercises 9. Advanced Flex and Bison Pure Scanners and Parsers Pure Scanners in Flex Pure Parsers in Bison Using Pure Scanners and Parsers Together A Reentrant Calculator GLR Parsing GLR Version of the SQL Parser C++ Parsers A C++ Calculator C++ Parser Naming A C++ Parser Interfacing a Scanner with a C++ Parser Should You Write Your Parser in C++ ? Exercises Appendix: SQL Parser Grammar and Cross-Reference Glossary Index

章節(jié)摘錄

插圖：A bison specification has the same three-part structure as a flex specification. （Flexcopied its structure from the earlier lex, which copied its structure from yacc, the predecessor of bison.） The first section, the definition section, handles control informationfor the parser and generally sets up the execution environment in which the parser willoperate. The second section contains the rules for the parser, and the third section isC code copied verbatim into the generated C program.Bison creates the C program by plugging pieces into a standard skeleton file. The rulesare compiled into arrays that represent the state machine that matches the input tokens.The actions have the SN and @N values translated into C and then are put into a switchstatement within yyparse0 that runs the appropriate action each time there's a reduction. Some bits of the skeleton have multiple versions from which bison chooses depending on what options are in use; for example, if the parser uses the locations feature,it includes code to handle location data.In this chapter we take the simple calculator example from Chapter 1 and extend itsignificantly. First, we rewrite it to take advantage of some handy bison shortcuts andchange it to produce a reusable data structure rather than computing the values on thefly. Later, we'll add more complex syntax for loops and functions and show how toimplement them in a simple interpreter.One of the most powerful data structures used in compilers is an abstract syntax tree（AST）. In Chapter 1 we saw a parse tree, a tree that has a node for every rule used toparse the input string. In most real grammars, there are rules that exist to managegrouping but that add no meaning to the program. In the calculator example, the rulesexp: term and term: factor exist only to tell the parser the relative precedence of theoperators. An AST is basically a parse tree that omits the nodes for the uninterestingrules.

媒體關(guān)注與評論

“我很高興看到John徹底詳盡地重寫這本經(jīng)典書。他更新的示例和說明，能夠幫助老用戶和新手?jǐn)[脫模仿那些已經(jīng)根深蒂固的舊lex和yacc?！?　　——Joel E. Denny bison維護(hù)人員

編輯推薦

《flex 與 bison(影印版)》是由東南大學(xué)出版社出版的。

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    flex 與 bison PDF格式下載

---