How grammar determine a language Context-free grammar rules determine the set of syntactically legal strings of token symbols for the structures defined by the rules For example the arithmetic expression (34-3)*42 Corresponds to the legal string of seven tokens (number-number )*number While (34-342 is not a legal expression, There is a left parenthesis that is not matched by a right parenthesis and the second choice in the grammar rule for an exp requires that parentheses be generated in pairs
How Grammar Determine a Language • Context-free grammar rules determine the set of syntactically legal strings of token symbols for the structures defined by the rules. – For example, the arithmetic expression • (34-3)*42 – Corresponds to the legal string of seven tokens • (number - number ) * number – While (34-3*42 is not a legal expression, • There is a left parenthesis that is not matched by a right parenthesis and the second choice in the grammar rule for an exp requires that parentheses be generated in pairs
Derivations Grammar rules determine the legal strings of token symbols by means of derivations a derivation is a sequence of replacements of structure names by choices on the right-hand sides of grammar rules a derivation begins with a single structure name and ends with a string of token symbols At each step in a derivation, a single replacement is made using one choice from a grammar rule
Derivations • Grammar rules determine the legal strings of token symbols by means of derivations • A derivation is a sequence of replacements of structure names by choices on the right-hand sides of grammar rules • A derivation begins with a single structure name and ends with a string of token symbols • At each step in a derivation, a single replacement is made using one choice from a grammar rule
Derivations The example exp >exp op exp (exp) number a derivation ()exp=> exp op exp e→即 cp op exp] (2)=> exp op number exp→ number ()=> exp *number (4)=>(exp)*number ex→>(ex)] (5)=>f exp op exp)*number (6)=>(exp op number )*number exp→> number] nber)* number[op→ (8)=>(number-number)*nu mber exp→ number] Derivation steps use a different arrow from the arrow meta-symbol in the grammar rules
Derivations • The example exp → exp op exp | (exp) | number op → + | – | * • A derivation (1) exp => exp op exp [exp → exp op exp] (2) => exp op number [exp → number] (3) => exp * number [op→ * ] (4) => ( exp ) * number [exp→ ( exp ) ] (5) =>{ exp op exp ) * number [exp → exp op exp} (6) => (exp op number) * number [exp→ number] (7) => (exp - number) * number [op → - ] (8) => (number - number) * number [exp → number] • Derivation steps use a different arrow from the arrow meta-symbol in the grammar rules
Language Defined by a grammar The set of all strings of token symbols obtained b derivations from the exp symbol is the language defined by the grammar of expressions L(G=sexp=>*s) G represents the expression grammar s represents an arbitrary string of token symbols (sometimes called a sentence) The symbols =>* stand for a derivation consisting of a sequence of replacements as described earlier (The asterisk is used to indicate a sequence of steps, much as it indicates repetition in regular expressions. Grammar rules are sometimes called productions Because they produce"the strings in L(G) via derivations
Language Defined by a Grammar The set of all strings of token symbols obtained by derivations from the exp symbol is the language defined by the grammar of expressions • L(G) = { s | exp =>* s } G represents the expression grammar s represents an arbitrary string of token symbols (sometimes called a sentence) The symbols =>* stand for a derivation consisting of a sequence of replacements as described earlier. (The asterisk is used to indicate a sequence of steps, much as it indicates repetition in regular expressions.) Grammar rules are sometimes called productions Because they "produce" the strings in L(G) via derivations
Grammar for a Programming Language The grammar for a programming language often defines a structure called program The language of this structure is the set of all syntactically legal programs of the programming language For example: a BNF for Pascal program ->program-heading: program-block program-heading→… program- block->.… The first rule says that a program consists of a program heading, followed by a semicolon, followed by a program block followed by a period
Grammar for a Programming Language • The grammar for a programming language often defines a structure called program • The language of this structure is the set of all syntactically legal programs of the programming language. – For example: a BNF for Pascal program → program-heading; program-block program-heading → …. program-block → ….. • The first rule says that a program consists of a program heading, followed by a semicolon, followed by a program block, followed by a period