Programming Languages

T E R M S

syntax: The branch of language study which treats of the combination of words and symbols into phrases.

Syntactic analysis (implemented by a parser) is the first step in compilation of a computer program.
Lexical analysis (implemented by a scanner) is usually a subprocess of syntactic analysis.

T E R M S

scanner: A program which identifies the tokens of a language.
token: An atomic symbol of the source program.
lexeme: The minimal lexical unit of a language

Lexical analysis, or scanning, analyses the source code as a stream of characters, identifies the tokens of the code, and passes those tokens to the scanner itself.
The lexical elements of a language can usually be described by regular expressions, which are simpler than BNF productions.
A scanner is usually implemented as a string pattern recognizer, based on the regular expressions of the tokens.
The lexical elements of a programming language are almost never recursive.

Example:
In the code

Net = Gross - Withholding;

the tokens are:

Net               (Identifier)
=                 (Assignment)
Gross             (Identifier)
-                 (Minus)
Withholding       (Identifier)
;                 (Semicolon)

T E R M S

parsing: The process of analyzing a source program syntactically to determine its phrase structure.
syntax tree: An ordered labeled tree such that: (a) the terminal nodes are labeled by terminal symbols; (b) the nonterminal nodes are labeled by by nonterminal symbols; and (c) each nonterminal node labeled by N has children labeled by X₁, ..., X_n
abstract syntax tree: A syntax tree generated by an abstract syntax.

¶ 4.3.1 Introduction to Parsing

T E R M S

parser: A program which identifies the phrase structure of a language.

A parser analyses the source code, and produces a representation of the syntactic structure of the program, usually as an abstract syntax tree.

¶ 4.3.2 Top-Down Parsers

T E R M S

top-down parser: A parser which starts at the starts at the root of the syntax tree and progressively analyses toward the leaves.

¶ 4.3.3 Bottom-Up Parsers

T E R M S

bottom-up parser: A parser which begins analysis at the leaves of the syntax tree and progresses toward the root.

¶ 4.3.3 The Complexity of Parsing

The syntax of a programming language is almost always recursive.

T E R M S

recursive-descent parser: A top-down parser which, beginning with the root phrase, calls recognizer functions for each phrase.
left-recursive grammar: A grammar which contains at least one left-recursive production.
left-recursive production: A production of a non-terminal phrase which which has the same non-terminal as its start.
LL(k) parser: A parser which parses the source from left to right and constructs a leftmost derivation of the sentence, looking ahead no more that k tokens.

LL(1) parsers are commonly referred to as simply LL parsers.
Example of left-recursive production:
```
<term> ::= <term> <addop> <factor>
```
This production is left recursive because the start of the production (<term>) is the same as the goal of the production (<term>).
LL parsers can be implemented as table driven state machines, or as recursive-descent parsers.
Table driven parsers have simple code, with the syntax of the language being parsed being contained in the parse table (which can be complex.)
Recursive descent parsers have complex code, with the syntax of the language being parsed being reflected in the algorithms of the parser.

¶ 4.4.1 The Recursive-Descent Parsing Process

Given the production

<expression> ::= <term> (<addop> <term>) *

A recursive-descent parser would have a function:

Phrase * ParseExpression () {
  Phrase * Term1;
  Phrase * Term2;
  Phrase * Operator;
  Term1 = ParseTerm ();
  while (Current.IsAddop) {
    Operator = ParseAddop ();
    Term2 = ParseTerm ();
    Term1 = new Term (Term1, Operator, Term2);
  }
  return Term1;
}

Given the production

<term> ::= <factor> (<mulop> <factor>) *

A recursive-descent parser would have a function:

Phrase * ParseTerm () {
  Phrase * Factor1;
  Phrase * Factor2;
  Phrase * Operator;
  Factor1 = ParseFactor ();
  while (Current.IsMulop) {
    Operator = ParseMulop ();
    Factor2 = ParseFactor ();
    Factor1 = new Term (Factor1, Operator, Factor2);
  }
  return Factor1;
}

Given the production

<factor> ::= '(' <expression> ')' | <Variable>

A recursive-descent parser would have a function:

Phrase * ParseFactor () {
  Phrase * Factor;
  if (Current.IsLeftParen) {
    TakeIt ();  // pass the leftparen;
    Factor = ParseExpression ();
    TakeIt (RightParen);
  } else {
    Factor = ParseVariable ();
  }
  return Factor;
}

Given the source code:

( a + b ) * c
The parser would (as partial pseudocode):
  Call ParseExpression;
    Call ParseTerm;
      Call ParseFactor;
        Call ParseExpression;  //  RECURSION

¶ 4.4.2 The LL Grammar Class

No left recursive grammar is LL(1).

T E R M S

semantics: The branch of language study which treats of meanings of symbols, words, and phrases.

¶ 4.5.1 The Parsing Problem for Bottom-Up Parsers

Left-recursive grammars can be parsed by bottom-up parsers.
Bottom-up parsers are are usually implemented as table driven state machines.
The parse table can be produced programmatically by "compiler-compilers".

¶ 4.5.2 Shift-Reduce Algorithms

An LR parser uses a stack to remember where it has been.
The table of an LR parser contains, for each state and next token,
- The next state
- The action to be taken (Shift or Reduce)
A shift action pushes the token and state onto the stack.
A reduce action pops tokens and states from the stack, and produces a phrase.

¶ 4.5.3 LR Parsers

T E R M S

LR(k) parser: A parser which parses the source from left to right and constructs a rightmost derivation of the sentence, looking ahead no more that k tokens.