Chapter 6

Question 1

What is syntax in the context of programming languages?

Answer 1

Syntax is the structure of a language—the rules that describe how tokens can be combined to form valid phrases, expressions, and programs.

Question 2

What is lexical structure?

Answer 2

Lexical structure is how characters form tokens like identifiers, keywords, literals, and operators.

Question 3

What is the purpose of scanning?

Answer 3

Scanning groups characters into tokens and removes whitespace/comments.

Question 4

What is the purpose of parsing?

Answer 4

Parsing checks token sequence against grammar and builds a parse tree or AST.

Question 5

Difference between scanner and parser?

Answer 5

Scanner makes tokens; parser checks structure and builds syntax tree.

Question 6

Common token categories?

Answer 6

Keywords, identifiers, literals, and special symbols.

Question 7

What is a reserved word?

Answer 7

A keyword that cannot be used as an identifier.

Question 8

What is a predefined identifier?

Answer 8

Identifier with built‑in meaning (library) but can technically be redefined.

Question 9

Are true/false/null keywords in Java?

Answer 9

They are literals, not keywords.

Question 10

Longest substring rule?

Answer 10

The scanner always chooses the longest sequence of characters that forms a valid token, rather than stopping early.

Question 11

What are delimiters?

Answer 11

Whitespace/tabs/newlines separating tokens.

Question 12

Indentation in Python vs C++/Java?

Answer 12

Python: syntactic; C++/Java: stylistic only.

Question 13

What is a free‑format language?

Answer 13

Layout doesn’t affect syntax (Java, C++).

Question 14

What is a fixed‑format language?

Answer 14

Column‑sensitive languages like old Fortran.

Question 15

What defines tokens formally?

Answer 15

Regular expressions.

Question 16

Basic reglar expression operations?

Answer 16

Concatenation, repetition, choice (|).

Question 17

[a‑z] meaning?

Answer 17

Any lowercase letter a through z.

Question 18

What does ? mean in regular expression?

Answer 18

Optional (0 or 1 occurrence).

Question 19

What does . mean in regular expression?

Answer 19

. can be any type of character (excluding newline) that can be inserted into the expression

Question 20

Meaning of (a|b)*c?

Answer 20

Any sequence of a/b ending with c.

Question 21

What is a context‑free grammar?

Answer 21

Tells you how strings in the language can be built, using rules that replace nonterminal symbols with sequences of terminals and/or nonterminals.

Question 22

What is Backus–Naur Form (BNF)?

Answer 22

BNF is a formal notation used to define a language’s grammar using nonterminals, terminals, and production rules.. Notation for grammars using ::= and |.

Question 23

Terminals vs nonterminals?

Answer 23

Nonterminals define structure; terminals are actual tokens.

Question 24

What is a production rule?

Answer 24

Replacement rule for a nonterminal.

Question 25

What is the start symbol?

Answer 25

First nonterminal that starts the expression

Question 26

Language of a grammar?

Answer 26

The set of all possible strings of terminals that can be generated from the start symbol by applying grammar rules.

Question 27

What is a derivation?

Answer 27

The process of repeatedly applying grammar rules until you end up with a string made entirely of terminals

Question 28

Why some issues are semantic?

Answer 28

Because Context Free Grammars can't express meaning-based constraints.

Question 29

What is a parse tree?

Answer 29

A tree diagram that shows how a grammar generates a string.

Question 30

Abstract Syntax Tree (AST)?

Answer 30

Simplified parse tree focusing on essential structure.

Question 31

Parse tree vs AST?

Answer 31

Parse tree shows full grammar; AST omits unnecessary nodes.

Question 32

Why use Abstract Syntax Tree (AST)s?

Answer 32

Simplifies semantic analysis and code generation.

Question 33

Ambiguous grammar?

Answer 33

A grammar is ambiguous if a single input can be parsed in more than one way

Question 34

Classic ambiguity example?

Answer 34

3 + 4 * 5 without precedence rules.

Question 35

Leftmost derivation?

Answer 35

Every step you expand the leftmost nonterminal first

Question 36

Using leftmost derivations for ambiguity?

Answer 36

Two different leftmost derivations = ambiguous.

Question 37

Operator precedence?

Answer 37

Operator precedence tells you which operations are higher priority and should be evaluated before others.

Question 38

Encoding precedence?

Answer 38

Encoding precedence means rewriting a grammar so that operator precedence is built into the grammar rules, removing ambiguity. Use expr/term/factor hierarchy.

Question 39

What is associativity?

Answer 39

Determines the order in which operators of the same precedence level are evaluated.

Question 40

Left recursion & associativity?

Answer 40

Left recursion → left‑associative.

Question 41

Right recursion & associativity?

Answer 41

Right recursion → right‑associative.

Question 42

What is EBNF?

Answer 42

Extended BNF adding { } and [ ].

Question 43

{ } in EBNF?

Answer 43

Means repetition: the enclosed pattern can appear zero or more times

Question 44

[ ] in EBNF?

Answer 44

Optional part.

Question 45

What is a syntax diagram?

Answer 45

Graph that show the grammar representation.

Question 46

Compiler?

Answer 46

Translates source code into machine code.

Question 47

What is a recognizer?

Answer 47

Parser that only checks if input is valid.

Question 48

Top‑down parsing?

Answer 48

Builds tree from root downward.

Question 49

Bottom‑up parsing?

Answer 49

Builds tree from leaves upward.

Question 50

Recursive descent?

Answer 50

Hand‑written top‑down parser with one function per nonterminal.

Question 51

Predictive (LL) parsing?

Answer 51

top-down method where the parser looks at the next token to immediately choose the correct grammar rule, without guessing

Question 52

Shift‑reduce parsing?

Answer 52

Shift-reduce parsing is a bottom-up method where the parser shifts tokens onto a stack and reduces them using grammar rules until it forms the start symbol.

Question 53

Parser generators?

Answer 53

Parser generators are tools that take a grammar and automatically produce a fully functioning parser, saving developers from writing parsing code manually.

Question 54

Manual vs generated parsers?

Answer 54

Manual: more control; generators: faster and safer.

Question 55

Lexics vs syntax vs semantics?

Answer 55

Lexics = tokens; syntax = structure; semantics = meaning.