Glossary action The C or C++ code associated with a flex pattern or a bison rule. When the pattern or rule matches an input sequence, the action code is executed. systems that run flex and bison use ASCII or extended 8-bit codes in the ISO-8859 series that include ASCII as a subset. bison A program that translates a dialect of BNF into LALR(1) or GLR parsers. alphabet A set of distinct symbols. For example, the ASCII character set is a collection of 128 dif- ferent symbols. In a flex specification, the alphabet is the native character set of the computer. In a bison grammar, the alphabet is the set of tokens and nonterminals used in the grammar. BNF Backus-Naur Form; a method of represent- ing context-free grammars. It is commonly used to specify formal grammars of pro- gramming languages. The input syntax of bison is a simplifed version of BNF. ambiguity An ambiguous grammar is one with more than one rule or set of rules that match the same input. In a bison grammar, ambiguous rules cause shift/reduce or reduce/reduce conflicts. The parsing mechanism that bison normally uses cannot handle ambiguous grammars. The programmer can use %prec declarations and bison's own internal rules to resolve conflicts when creating a parser, or the programmer can use a GLR parser, which can handle ambiguous grammars directly. compiler A program that translates a set of instruc- tions (a program) in one language into some other representation; typically, the output of a compiler is in the native binary language that can be run directly on a computer. Compare to interpreter. conflict An error within the bison grammar in which two (or more) parsing actions are possible when parsing the same input token. There are two types of conflicts: shift/reduce and reduce/reduce. (See also ambiguity.) ASCII American Standard Code for Information Interchange; a collection of 128 symbols representing the common symbols found in the American alphabet: lowercase and up- percase letters, digits, and punctuation, plus additional characters for formatting and control of data communication links. Most context-free grammar A grammar in which each rule has a single symbol on the LHS; hence, one in which the RHS can match input regardless of what might precede or follow the material it matches. Also called a phrase structure grammar. Context-sensitive grammars, containing rules with several symbols on the 259