Compilers

What is commonly used to express the rules for recognizing tokens in lexical analysis?

  1. AFloating-point rounding rules
  2. BRegular expressions, processed by finite automata
  3. CCache replacement policies
Show answer and explanation

Answer: B. Regular expressions, processed by finite automata

Token types can be written concisely as regular expressions, such as "a letter followed by letters or digits" for identifiers and "one or more digits" for numbers. Regular expressions convert to finite automata, machines with a finite number of states that change state with each character read, so tokens are extracted in time proportional to input length. Lexers are therefore often generated automatically from regular expressions by tools. Rounding and cache rules have nothing to do with lexical analysis.

  • A. Rounding rules concern numerical computation.
  • B. Correct. Rules are written as regular expressions and processed by finite automata.
  • C. Cache replacement concerns the memory hierarchy.
Practice this topic Back to topic

More Compilers questions

  1. Which kind of grammar is used to describe most programming languages and underlies parsing?
  2. What does the abstract syntax tree for the expression 2 + 3 * 4 look like?
  3. Which describes three-address code, a kind of intermediate representation?
  4. What does liveness analysis, done in preparation for register allocation, determine?
  5. In a function, at most five values are live at the same time. In a simple case where the interference graph imposes no further constraints, how many registers are needed at minimum to hold every value without spilling?