PLC Chapter 4

What is lexical analysis?

The process of identifying substrings of source code called lexemes and converting them into tokens.

What is a lexical analyzer?

A low-level pattern matcher for character strings that acts as the front end for the parser.

What is a syntax analyzer (parser)?

A high-level analyzer that checks the grammatical structure of a token sequence and produces a parse tree.

What mathematical model and grammar are associated with lexical analysis?

A finite automaton (FA) based on a regular grammar.

What mathematical model and grammar are associated with syntax analysis?

A push-down automaton (PDA) based on a context-free grammar (CFG or BNF).

What is BNF?

Backus–Naur Form, a formal notation used to describe the syntax of a programming language through grammar rules.

What are the three advantages of using BNF?

It provides a clear and concise syntax description; the parser can be based directly on the BNF; parsers based on BNF are easy to maintain.

What are the three reasons for separating lexical and syntax analysis?

Simplicity, efficiency, and portability.

How does separating lexical and syntax analysis improve simplicity?

Less complex approaches can be used for lexical analysis, which simplifies the parser.

How does separating lexical and syntax analysis improve efficiency?

The lexical analyzer can be optimized independently.

How does separating lexical and syntax analysis improve portability?

Parts of the lexical analyzer may not be portable, but the parser is portable.

What is a lexeme?

The actual sequence of characters that matches a character pattern.

What is a token?

The lexical category associated with a lexeme.

What is the difference between a lexeme and a token?

A lexeme is the actual character sequence, whereas a token is its category.

What are the lexemes and tokens in sum + 47?

sum is IDENT; + is ADD_OP; 47 is INT_LIT.

What does a lexical analyzer produce from a character stream?

A token stream, which is passed to the parser.

What is the difference between the purpose of a lexical analyzer and a parser?

The lexical analyzer identifies individual components of the source code, while the parser determines how those components fit together according to the grammar.