Plc Test 2

Front 1

Syntax Analyzer

Back 1

Checks the syntax of a program and creates a parse tree from it.

Front 2

Advantages of using BNF

Back 2

BNF descriptions are clear and concise, both for humans and software systems.
Syntax analyzers can be generated directly from BNF.
Implementations based on BNF are easy to maintain

Front 3

The two distinct parts of analyzing syntax

Back 3

1) The lexical analyzer deals with small-scale language constructs, such as names and numeric literals.

2) The syntax analyzer deals with large-scale constructs, such as expressions, statements, and program units.

Front 4

Reasons for the separation of the two parts of analyzing syntax

Back 4

Simplicity—Removing the details of lexical analysis from the syntax analyzer
makes it smaller and less complex.
Efficiency—It beomes easier to optimize the lexical analyzer.
Portability—The lexical analyzer reads source files, so it may be platformdependent.

Front 5

A lexical analyzer collects input characters into groups (Called what?) and assigns an
internal code (Called what?) to each group.

Back 5

1) Lexemes
2) Token

Front 6

How are Lexemes recognized?

Back 6

By matching the input against patterns

Front 7

What are the Tokens and lexemes of this statement?

result = oldsum - value / 100;

Back 7

Token Lexeme
IDENT result
ASSIGN_OP =
IDENT oldsum
SUB_OP -
IDENT value
DIV_OP /
INT_LIT 100
SEMICOLON ;

Front 8

Other tasks performed by a lexical analyzer?

Back 8

Skipping comments and white space between lexemes.
Inserting lexemes for user-defined names into the symbol table.
Detecting syntactic errors in tokens, such as ill-formed floating-point literals.

Front 9

Approaches to building a lexical analyzer:

Back 9

Write a formal description of the token patterns of the language and use a software tool such as lex to automatically generate a lexical analyzer.
Design a state transition diagram that describes the token patterns of the language and write a program that implements the diagram.
Design a state transition diagram that describes the token patterns of the language and hand-construct a table-driven implementation of the state diagram

Front 10

A state transition diagram, or state diagram, is a directed graph

Back 10

The nodes are labeled with state names.
The arcs are labeled with input characters.
An arc may also include actions to be done when the transition is taken.

Front 11

Syntax analysis is often referred to as:

Back 11

Parsing

Front 12

Top-down parsers

Back 12

Build the tree from the root downward to the leaves.

Front 13

Bottom-up parsers

Back 13

Build the tree from the leaves upward to the root.

Front 14

Terminal symbols convention

Back 14

Lowercase letters at the beginning of the alphabet (a, b, …)

Front 15

Nonterminal symbols convention

Back 15

Uppercase letters at the beginning of the alphabet (A, B,
…)

Front 16

Terminals or nonterminals convention

Back 16

Uppercase letters at the end of the alphabet (W, X,
Y, Z)

Front 17

Strings of terminals convention

Back 17

Lowercase letters at the end of the alphabet (w, x, y, z)

Front 18

Mixed strings (terminals and/or nonterminals) convention

Back 18

Lowercase Greek letters (α, β,
γ, δ)

Front 19

A top-down parser traces or builds the parse tree:

Back 19

Traces or builds the parse tree in preorder: each node is visited
before its branches are followed.

Front 20

The actions taken by a top-down parser correspond to a

Back 20

Actions correspond to a leftmost derivation

Front 21

recursive-descent parser

Back 21

coded directly from the BNF description of the
syntax of a language.
An alternative is to use a parsing table rather than code

Front 22

LL algorithm

Back 22

The first L in LL specifies a left-to-right scan of the input; the second L specifies that a leftmost derivation is generated.

Front 23

A bottom-up parser constructs a parse tree by:

Back 23

Constructs a parse tree by beginning at the leaves and progressing toward the root.

Front 24

The actions taken by a botom-up parser correspond to a

Back 24

Actions correspond to a right-most derivation

Front 25

Handle

Back 25

The correct RHS to reduce

Front 26

Recursive-descent parser

Back 26

consists of a collection of subprograms, many of
which are recursive; it produces a parse tree in top-down order.

Front 27

A Recursive-descent parser has

Back 27

has one subprogram for each nonterminal in the
grammar.

Front 28

Pairwise disjointness test

Back 28

is used to test a non-left-recursive grammar to
determine whether it can be parsed in a top-down fashion. This test requires
computing FIRST sets, where
FIRST(α) = {a | α =>* aβ}
The symbol =>* indicates a derivation of zero or more steps. If α =>* ε, then ε
is also in FIRST(α), where ε is the empty string.

Front 29

Shift-reduce algorithms

Back 29

Bottom-up parsers are often called this, because shift and
reduce are their two fundamental actions.

Front 30

The shift action

Back 30

moves the next input token onto the parser’s stack.

Front 31

A reduce action

Back 31

replaces a RHS (the handle) on top of the parser’s stack by its
corresponding LHS.

Front 32

Most bottom-up parsing algorithms belong to the

Back 32

belong to the LR family. LR parsers use a
relatively small amount of code and a parsing table.

Front 33

The original LR algorithm was designed by

Back 33

designed by Donald Knuth, who published it in
1965

Front 34

Canonical LR algorithm

Back 34

was not widely used because producing the
parsing table required large amounts of computer time and memory.

Front 35

Advantages of LR parsers:

Back 35

They can be built for all programming languages.
They can detect syntax errors as soon as possible in a left-to-right scan.
The LR class of grammars is a proper superset of the class parsable by LL parsers.

Front 36

LR Parser

Back 36

type of bottom-up parsers. he L means that the parser reads input text in one direction without backing up; that direction is typically Left to right within each line, and top to bottom across the lines of the full input file. (This is true for most parsers.) The R means that the parser produces a reversed Rightmost derivation; it does a bottom-up parse, not a top-down LL parse or ad-hoc parse.

Front 37

the parser can avoid examining the entire stack if

Back 37

it keeps a summary of the stack contents in a “state” symbol on top of the stack.

Front 38

Knuth’s insight was that it was only necessary to look to the

Back 38

left of the suspected
handle (by examining the stack) to determine whether it was the handle.

Front 39

An LR parser configuration

Back 39

a pair of strings representing the stack and the
remaining input:
(S0Xl
SlX2
S2…XmSm, a
i
a
i+1…an
$)
The dollar sign is an end-of-input marker.

Front 40

The LR parsing process is based on the parsing table, which has two parts:

Back 40

ACTION and GOTO.

Front 41

The ACTION part has

Back 41

has state symbols as its row labels and terminal symbols as its
column labels.

Front 42

The two primary actions are

Back 42

shift (shift the next input symbol onto the stack) and
reduce (replace the handle on top of the stack by the LHS of the matching rule).

Front 43

Two other actions are possible:

Back 43

accept (parsing is complete) and error (a syntax
error has been detected).

Front 44

Informal definition of parser actions:

Back 44

Shift: The next input symbol is pushed onto the stack, along with the state symbol specified in the ACTION table.

Reduce: First, the handle is removed from the stack. For every grammar symbol
on the stack there is a state symbol, so the number of symbols removed is twice
the number of symbols in the handle. Next, the LHS of the rule is pushed onto
the stack. Finally, the GOTO table is used to determine which state must be
pushed onto the stack.

Accept: The parse is complete and no errors were found.

Error: The parser calls an error-handling routine.