Compilers

Which kind of grammar is used to describe most programming languages and underlies parsing?

  1. ARegular grammars only
  2. BNatural-language grammar
  3. CContext-free grammars
Show answer and explanation

Answer: C. Context-free grammars

Nested parentheses and if statements inside if statements cannot be expressed with regular expressions. Most programming-language grammars are written as context-free grammars, collections of rewriting rules such as "expr → expr + term", and parsing is based on them. Parsing methods include LL, which applies rules top-down, and LR, which builds bottom-up, and tools can generate parsers from grammars automatically. Regular grammars suit lexical analysis and cannot handle nesting.

  • A. Regular grammars cannot express structures such as nested parentheses.
  • B. Programming languages are not defined by natural-language grammar.
  • C. Correct. Parsing is based on context-free grammars.
Practice this topic Back to topic

More Compilers questions

  1. What does the abstract syntax tree for the expression 2 + 3 * 4 look like?
  2. Which describes three-address code, a kind of intermediate representation?
  3. What does liveness analysis, done in preparation for register allocation, determine?
  4. 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?
  5. If a loop with 100 iterations is unrolled by replicating its body four times, how many counter checks and branches remain? (Assume 100 is divisible by 4.)