book

flex & bison

by John Levine

August 2009

Intermediate to advanced

292 pages

7h 31m

English

O'Reilly Media, Inc.

Read now

Unlock full access

Scope of This BookConventions Used in This BookGetting Flex and BisonThis Book’s Example FilesUsing Code ExamplesSafari® Books OnlineHow to Contact UsAcknowledgments
Lexical Analysis and ParsingRegular Expressions and ScanningOur First Flex ProgramPrograms in Plain FlexPutting Flex and Bison TogetherThe Scanner as CoroutineTokens and ValuesGrammars and ParsingBNF GrammarsBison’s Rule Input LanguageCompiling Flex and Bison Programs TogetherAmbiguous Grammars: Not QuiteAdding a Few More RulesFlex and Bison vs. Handwritten Scanners and ParsersExercises
Regular ExpressionsRegular Expression ExamplesHow Flex Handles Ambiguous PatternsContext-Dependent TokensFile I/O in Flex ScannersReading Several FilesThe I/O Structure of a Flex ScannerInput to a Flex ScannerFlex Scanner OutputStart States and Nested Input FilesSymbol Tables and a Concordance GeneratorManaging Symbol TablesUsing a Symbol TableC Language Cross-ReferenceExercises
How a Bison Parser Matches Its InputShift/Reduce ParsingWhat Bison’s LALR(1) Parser Cannot ParseA Bison ParserAbstract Syntax TreesAn Improved Calculator That Creates ASTsLiteral Character TokensBuilding the AST CalculatorShift/Reduce Conflicts and Operator PrecedenceWhen Not to Use Precedence RulesAn Advanced CalculatorAdvanced Calculator ParserCalculator Statement SyntaxCalculator Expression SyntaxTop-Level Calculator GrammarBasic Parser Error RecoveryThe Advanced Calculator LexerReserved WordsBuilding and Interpreting ASTsEvaluating Functions in the CalculatorUser-Defined FunctionsUsing the Advanced CalculatorExercises
A Quick Overview of SQLRelational DatabasesManipulating RelationsThree Ways to Use SQLSQL to RPNThe LexerScanning SQL KeywordsScanning NumbersScanning Operators and PunctuationScanning Functions and NamesComments and MiscellanyThe ParserThe Top-Level Parsing RulesSQL ExpressionsFunctionsOther expressionsSelect StatementsSelect options and table referencesSELECT table referencesDelete StatementInsert and Replace StatementsReplace statementUpdate StatementCreate DatabaseCreate TableUser VariablesThe Parser RoutinesThe Makefile for the SQL ParserExercises
Structure of a Flex SpecificationDefinition SectionRules SectionUser SubroutinesBEGINC++ ScannersContext SensitivityLeft ContextRight ContextDefinitions (Substitutions)ECHOInput ManagementStdio File ChainingInput BuffersInput from StringsFile Nestinginput()YY_INPUTFlex LibraryInteractive and Batch ScannersLine Numbers and yylinenoLiteral BlockMultiple Lexers in One ProgramCombined LexersMultiple LexersOptions When Building a ScannerPortability of Flex LexersPorting Generated C LexersBuffer sizesCharacter setsReentrant ScannersExtra Data for Reentrant ScannersAccess to Reentrant Scanner DataReentrant Scanners, Nested Files, and Multiple ScannersUsing Reentrant Scanners with BisonRegular Expression SyntaxMetacharactersREJECTReturning Values from yylex()Start Statesunput()yyinput() yyunput()yylengyyless()yylex() and YY_DECLyymore()yyrestart()yy_scan_string and yy_scan_bufferYY_USER_ACTIONyywrap()
Structure of a Bison GrammarSymbolsDefinition SectionRules SectionUser Subroutines SectionActionsEmbedded ActionsSymbol Types for Embedded ActionsAmbiguity and ConflictsTypes of ConflictsShift/Reduce ConflictsReduce/Reduce Conflicts%expectGLR ParsersBugs in Bison ProgramsInfinite RecursionInterchanging PrecedenceEmbedded ActionsC++ Parsers%code BlocksEnd MarkerError Token and Error Recovery%destructorInherited Attributes ($0)Symbol Types for Inherited Attributes%initial-actionLexical FeedbackLiteral BlockLiteral TokensLocations%parse-paramPortability of Bison ParsersPorting Bison GrammarsPorting Generated C ParsersLibrariesCharacter CodesPrecedence and Associativity DeclarationsPrecedenceAssociativityPrecedence DeclarationsUsing Precedence and Associativity to Resolve ConflictsTypical Uses of PrecedenceRecursive RulesLeft and Right RecursionRulesSpecial Characters%start DeclarationSymbol ValuesDeclaring Symbol TypesExplicit Symbol TypesTokensToken NumbersToken Values%type Declaration%union DeclarationVariant and Multiple GrammarsCombined ParsersMultiple ParsersUsing %name-prefix or the -p FlagLexers for Multiple ParsersPure Parsersy.output FilesBison Librarymain()yyerror()YYABORTYYACCEPTYYBACKUPyyclearinyydebug and YYDEBUGYYDEBUGyydebugyyerrokYYERRORyyerror()yyparse()YYRECOVERING()
The Pointer Model and ConflictsKinds of ConflictsParser StatesContents of name.outputReduce/Reduce ConflictsShift/Reduce ConflictsReview of Conflicts in name.outputCommon Examples of ConflictsExpression GrammarsIF/THEN/ELSENested List GrammarHow 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)SummaryExercises
Error ReportingLocationsAdding Locations to the ParserAdding Locations to the LexerMore Sophisticated Locations with FilenamesError RecoveryBison Error RecoveryFreeing Discarded SymbolsError Recovery in Interactive ParsersWhere to Put Error TokensCompiler Error RecoveryExercises

Pure Scanners and ParsersPure Scanners in FlexPure Parsers in BisonUsing Pure Scanners and Parsers TogetherA Reentrant CalculatorGLR ParsingGLR Version of the SQL ParserC++ ParsersA C++ CalculatorC++ Parser NamingA C++ ParserInterfacing a Scanner with a C++ ParserShould You Write Your Parser in C++ ?Exercises

Content preview from flex & bison

Preface

Flex and bison are tools designed for writers of compilers and interpreters, although they are also useful for many applications that will interest noncompiler writers. Any application that looks for patterns in its input or has an input or command language is a good candidate for flex and bison. Furthermore, they allow for rapid application prototyping, easy modification, and simple maintenance of programs. To stimulate your imagination, here are a few things people have used flex and bison, or their predecessors lex and yacc, to develop:

The desktop calculator bc
The tools eqn and pic, typesetting preprocessors for mathematical equations and complex pictures
Many other “domain-specific languages” targeted for a particular application
PCC, the Portable C Compiler used with many Unix systems
Flex itself
A SQL database language translator

Scope of This Book

Chapter 1, Introducing Flex and Bison, gives an overview of how and why flex and bison are used to create compilers and interpreters and demonstrates some simple applications including a calculator built in flex and bison. It also introduces basic terms we use throughout the book.

Chapter 2, Using Flex, describes how to use flex. It develops flex applications that count words in files, handle multiple and nested input files, and compute statistics on C programs.

Chapter 3, Using Bison, gives a full example using flex and bison to develop a fully functional desktop calculator with variables, procedures, loops, and conditional expressions. ...