../

Levine, Mason, Brown - Lex & Yacc

20260924T184756-lex_and_yacc_flashcard

Chapter 1

  • Division into the smallest meaningful units is called lexing
  • lex takes in the a description and produces a C routine called a lexical analyzer or a lexer or a scanner.
  • This description is called the lex specification. It is usually in form of regular expressions.
  • lex lexer is faster than any hand written one.
  • Parsing is the processes of understanding the relationship between the tokens.
  • The specification given to the parser is called a grammar.
  • yacc takes a grammar and produces a C routine called a parser.
  • yacc parser is usually not as fast as a hand written one
    • But the ease of use outweighs this performance hit
    • You also cannot be sure that your hand written parser only recognizes the grammar that you provided and nothing else.

Structure of a lex program

DEFINITIONS
%%
RULES
%%
USER SUBROUTINES

lex disambiguation rules

  • Patterns only match a string once
  • If multiple rules match the current input, the rule with the longest matching prefix is selected.

These two rules are enough to have an unambiguous specification.