22277 - Compilers Parsing

| Syllabus | Contact Info | Computer Club |

Herbert J. Bernstein Professor of Computer Science
Dept. of Mathematics and Computer Science, 150 Idle Hour Blvd., KSC 121, Oakdale, NY 11769-1999

22277 CSC 3149A -- Compilers -- Spring 2009
Thursday 5:30 pm -- 8:11 pm KSC 102A
Parsing Programming Languages

This web page is http://www.bernstein-plus-sons.com/.dowling/CSC3149S09/Prog_Lang_Parse.html
Copyright © 2009 Herbert J. Bernstein and other parties. All rights reserved.

Computer Programming Languages -- Parsing Computer Programming Languages -- Parsing

By Herbert J. Bernstein

The following are some supplemental notes on defining and parsing of Computer Programming Languages.

The defining and parsing of languages has a long and complex history, but current "industrial" practice by most programmers is based on use of commonly available tools for lexical scanning of tokens and parsing of grammars based on:

S. C. Johnson, YACC: Yet another Compiler-Compiler in UNIX Programmer's Manual, Supplementary Documents, 4.2 Berkeley Software Distribution, Virtual VAX-11 Version, March 1984, CSD, Dept. of EE and CS, U. of California, Berkeley, CA, originally published as Computer Science Technical Report No. 32, 1975, Bell Laboratories, Murray Hill, NJ.
M. E. Lesk and E. Schmidt, Lex - A Lexical Analyzer Generator in UNIX Programmer's Manual, Supplementary Documents, 4.2 Berkeley Software Distribution, Virtual VAX-11 Version, March 1984, CSD, Dept. of EE and CS, U. of California, Berkeley, CA, originally published as Computer Science Technical Report No. 39, 1975, Bell Laboratories, Murray Hill, NJ.

Two highly accessible descendants of these programs are

R. Corbett et. al bison and

V. Paxson et. al flex

Syntax

Productions, types of grammars

Productions are rules for constructing sentences in a language

Terminal symbols are what actually appear in the language
Non-terminal symbols are the higher level constructs of the language, e.g. sentences, clauses, etc.
May be used to infer rules for parsing the language

Chomsky hierarchy

Type 0 -- (unrestricted) arbitrary strings on both sides of productions
Type 1 -- (context sensitive) |lhs| < |rhs|
Type 2 -- (context free) single non-terminal symbol on the lhs
Type 3 -- (regular) A single optional non-terminal on the left (left linear) or right (right linear) of rhs with a terminal symbol

BNF, parse trees, diagrams, EBNF

BNF

context free grammar, lhs ::= rhs
<> delimit non-terminals, bold or quotes for terminals, or "as is"
vertical bar for alternatives

Parse trees trace the flow of analysis of a sentence

Ambiguity = multiple parse trees for the same sentence

Syntax diagrams convey the same information about productions (think RR tracks)

EBNF

Square brackets, curly braces or parentheses for optional components, with various suffixes (*, + ?) for repetition counts

Many conflicting variants. See http://www.cs.man.ac.uk/~pjj/bnf/bnf.html#EBNF

Parsing issues and precedence

Ambiguity -- alternative ways to parse the same sentence
Resolve with left-right, right-left and operator precedence rules

Semantics

Difficult to convey meanings rigorously
Actions embedded in rules used to enforce semantics

Language Translation

Preprocessing and multipass translation
Parsing

Top-Down (Start with start symbol, find the sentence)
Bottom-Up (Start with the sentence, find the start symbol)
Desirable to restrict grammar to save time in parsing

Lexical scanning
Code generation, optimization

22277 CSC 3149A -- Compilers -- Spring 2009 Thursday 5:30 pm -- 8:11 pm KSC 102A Parsing Programming Languages

22277 CSC 3149A -- Compilers -- Spring 2009
Thursday 5:30 pm -- 8:11 pm KSC 102A
Parsing Programming Languages