CS 345 slide 9 Spring 200518 January 20052. procedural decompositionfor each x  list doif x appears earlier in list thenoutput (x)or (using an auxiliary table)for each x  list doif find( table, x ) thenoutput (x)elseinsert( table, x )Advantages• the package (table, find, insert) can be designedseparately from calling routine• may produce first output sooner than (1)Common terms for the solutions’ structures:1. producer-consumer:sort produces list elements findAdjacentDuplicates consumes them2. client-server:(table, find, insert) provides a service thatis used by the caller (client)CS 345 slide 10 Spring 200518 January 2005Syntactic structurePerhaps FORTRAN’s most prominent feature (includedin nearly all subsequent languages):the arithmetic expression— a major advance over assembler notation:1. mathematical notation’s familiarity2. support for modularizationConsider an arithmetic expression of the formE + Fwhere E and F may themselves be simple or complexarithmetic expressions.(1) The meaning of this whole expression can be understoodwholly in terms of an understanding of the meanings ofE and F [and (+)];(2) the purpose of each part consists solely in itscontribution to the purpose of the whole;(3) the meaning of the two parts can be understood whollyindependently of each other;(4) If E or F is an arithmetic expression, the same struc-turing principle can be applied to the analysis of theparts as is applied to the understanding of the whole.(5) the interface between the parts is clear, narrow, and wellcontrolled: in this case just a single number;(6) the separation of the parts, and their relation to thewhole, are apparent from their written form.— C. A. R. Hoare, “Hints on programming-language design”in Essays in Computing Science (Prentice-Hall, 1989)CS 345 slide 11 Spring 200518 January 2005Expression notations come in several flavors; we’llexamine four.The purpose of every expression notation is tospecify the relationships between expressions’ parts.Since expressions consist of operators and operands,an expression notation must specify which operand(s) belong to each operator.Conventional arithmetic expressions employ amixture of infix, prefix, and postfix notation:infix (mostly): –b +  (b^2 – 4 a c)• each (dyadic) operator lies between its operandsTwo less conventional notations: prefix and postfixprefix:+ –1 b  –2 ^ b 2   4 a c • each operator precedes its operand(s)postfix: b –1 b 2 ^ 4 a  c  –2  +• each operator follows its operand(s)Infix notation needs associativity, precedence, andparentheses to resolve ambiguities.CS 345 slide 12 Spring 200518 January 2005In infix notation, precedence and associativity comeinto play when an operand occurs between twooperators.Example:a + b  cTo which operator does b belong?• If the operators precedences are different, thehigher one wins.• When the operators’ precedences are equal, thequestion is settled by their associativity (left orright); examples:a + b + c, a – b – c, a / b  cPrefix and postfix are simpler— precedence,associativity, and parentheses are all unnecessary:To interpret a postfix expression such as 16 24 + 97 53 – all we need to know is each operator’s arity.——————Possible confusion: In mathematics, some operators areknown as associative. An example is (+) on real numbers: Forall reals a, b, and c,(a+b) + c = a + (b+c)This mathematical associativity is a semantic property of(+) —i.e., it’s a consequence of what (+) is defined to mean. Incontrast, left-associativity and right-associativity arepurely syntactic properties, having nothing to do withoperators’ meaning.  an operator’s arity is the number of operands it takes. If the arity isnot fixed (as in Lisp) then parentheses are required.CS 345 slide 13 Spring 200518 January 2005Abstract Syntax TreesConsider the expressions infix prefix postfix(a)+(b–c) +  a – b ca  b c – +The concrete expressions —that is, the sequences ofsymbols on the page— are all different, but theirabstract structure is the same.Abstractly speaking, an expression is one of thefollowing: • a name • a numeral • an expression with a unary operation • a pair of expressions with a binary operation.This is an abstract syntax: for each kind of expres-sion, it specifies its constituent parts, but it does notspecify how the parts are arranged.How can an expression’s abstract structure beexpressed independent of any concrete representa-tion?It can be depicted as an abstract syntax tree: Each subtree  a subexpression.each subtree’s root  the subexpr’s operatoreach root’s children  the operands+–a b cCS 345 slide 14 Spring 200518 January 2005Aside: Traversing an expression’s abstract syntaxtree … in preorderpostorder yields a prefixpostfix expressionAn inorder traversal gives an infix expression, butevery subexpression must be parenthesized.Each node’s degree depends on its operator’s arity.Example: two versions of an arity–3 operator:if cond then exp0 else exp1 (ML)cond ? exp0 : exp1 (C/C++)and their abstract syntax tree:ifcond exp0 exp1Observation:When we draw an abstract syntax tree, we’re reallycreating another concrete expression notation—albeit a two-dimensional one.—————CS 345 slide 15 Spring 200518 January 2005GrammarsHow can the syntax of a given notation be specifiedprecisely, so that people can understand it andcompilers can implement it?The usual means of specifying a programminglanguage’s concrete syntax is a set of rules called itsgrammar.A grammar is given in a meta-notation (which is anotation that is used in defining another notation).A context-free grammar (the most common anduseful kind for programming languages) consists of1. atomic symbols (terminals)2. variables (nonterminals)3. productions define each nonterminal as asequence of terminals and nonterminals4.a starting nonterminalThe most popular notations for context-freegrammars are• BNF (“Backus-Naur Form”)• Extended BNF• Syntax charts (“railroad diagrams”)CS 345 slide 16 Spring 200518 January 2005BNF grammar notation• each nonterminal is enclosed in  • production: nonterminal ::= sequence …• empty sequence: empty• alternatives are separated by ‘|’•