Class Notes Sept 30

CS 451-651

Notes: Sept 30

Topics:

Subclass implementation in Java/C++, in response to question about how to declare inter-Node pointers.
Discussion of alternate strategies for implementation of StmtList
Presentation of LALR parser at work
explanation of C declaration grammar problem with 'typedef_name"
Looking forward: data types and semantic analysis

Subclass implementation

How memory is laid out for parent and subclasses
How visibility is controlled by declared (or cast) type of pointer (runtime check on cast by Java)

For compiler, unlikely to look into attributes of nodes during construction of tree, so no particular gain in having 'terminal' symbols closely declared with exact subtype. Within Node classes, though, best to be precise.

StmtList implementation

Can use ArrayList
(is there an O(n**2) algorithm here as the array is grown? Potentially, though Java is clever: lengthen array by doubling size each time -> log n behavior)

or Can use threaded list
(with list, need to maintain separate 'end' pointer to allow efficient appending of new items)

Your choice. Either way, there will have to be a separate class "StmtList" to hold the header.

LALR Parser

PowerPoint animation of example from textbook.

C 'typedef_name' problem
Published grammar is ambiguous if

      typedef_name ::= identifier;

Turns out to be due to right-recursive rule for declaration_specifiers. Interesting to see how parser gets in trouble if it does the shift for the wrong case.

Data Types

Variables have types - from declarations
Types are propagated upward in tree. Concept of input and output types for each node
Will need to check. Language design governs what you do ... insert conversions or report an error.

We will be implementing simple declarations.
Need to discuss how to represent "type".

Misc

Suggest adding a null statement for your convenience.
(recall that parser needs to be one token ahead)

Suggest adding print statement for convenience. No rush, not essential till we get to execution.

   Stmt ::=   PRINT expr SEMI ;

In class, using CamelCase name convention, as in Java API. You should use some consistent convention, probably less confusing to use same one as in lecture.