BNF GrammarForm of BNF rulesNotes on terminologyUses of a grammarGenerating sentencesDevelopment approachesRequirements and constraintsFirst cutFirst cut: EvaluationSecond cut: OverviewSecond cut: More detailSecond cut: EvaluationThird (very brief) cutFourth cut, not quite as briefLetting go of a constraintFifth (and final) cutExplanation I of final BNF APIExplanation II of final BNF APIFinal version: EvaluationMoralsAside: Tokenizing the input grammarThe EndJan 14, 2019BNF GrammarExample design of a data structureForm of BNF rules<BNF rule> ::= <nonterminal> "::=" <definitions><nonterminal> ::= "<" <words> ">"<terminal> ::= <word> | <punctuation mark> | ' " ' <any chars> ' " '<words> ::= <word> | <words> <word><word> ::= <letter> | <word> <letter> | <word> <digit><definitions> ::= <definition> | <definitions> "|" <definition><definition> ::= <empty> | <term> | <definition> <term><empty> ::=<term> ::= <terminal> | <nonterminal>Not defined here (but you know what they are) : <letter>, <digit>, <punctuation mark>, <any chars> (any printable nonalphabetic character except double quote)Notes on terminologyA grammar typically has a “top level” elementA string is a “sentential form” if it satisfies the syntax of the top level elementA string is a “sentence” if it is a sentential form and is composed entirely of terminalsA string “belongs to” a grammar if it satisfies the rules of that grammarUses of a grammarA BNF grammar can be used in two ways:To generate strings belonging to the grammarTo do this, start with a string containing a nonterminal;while there are still nonterminals in the string { replace a nonterminal with one of its definitions}To recognize strings belonging to the grammarThis is the way programs are compiled--a program is a string belonging to the grammar that defines the languageRecognition is much harder than generationGenerating sentencesI want to write a program that reads in a grammar, stores it in some appropriate data structure, then generates random sentences belonging to that grammarI need to decide:How to store the grammarWhat operations to provide on the grammarThese decisions are intertwined!How I store the grammar determines what operations are easy and efficient (and even possible!)Development approachesBad approach:Design a general representation for grammars and a complete set of operations on themActually, this is a good approach if you are writing a general-purpose package for general use--for example, for inclusion in the Java APIOtherwise, it just makes your program much more complexGood approach:Decide the operations you need for this program, and design a representation for grammars that supports these operationsIt’s a nice bonus if the design can later be extended for other purposesRemember the Extreme Programming slogan YAGNI: “You ain’t gonna need it.”Requirements and constraintsWe need to read the grammar inBut we don’t need to modify it laterAny tools for building the grammar structure can be privateWe need to look up the definitions of nonterminalsWe need this because we will need to replace each nonterminal with one of its definitionsWe need to know the top level element of the grammarBut we can just assume that we know what it isFor example, we can insist that the top-level element be <sentence>First cutpublic class Grammar implements Iterable List<String> rule; // a single alternative for a nonterminal List<List<String>> definition; // all the rules for one nonterminal Map<String, List<List<String>>> grammar; // rules for all the nonterminals public Grammar() { grammar = new TreeMap<String, List<String>>(); } public void addRule(String rule) throws IllegalArgumentException public List<List<String>> getDefinition(String nonterminal) public List<String> getOneRule(String nonterminal) // random choice public Iterator iterator() public void print()First cut: EvaluationAdvantagesSmall, easily learned interfaceJust one classCan be made to workDisadvantagesAs designed, <foo> ::= bar | baz is two rules, requiring two calls to addRule; hence requires caller to do some of the parsing, to separate out the left-hand sideRequires some fairly complicated use of genericsArrayList implements List (hence is a List), but consider: List<List<String>> definition = makeList();This statement is legal if makeList() returns an ArrayList<List<String>>It is not legal if makeList() returns an ArrayList<ArrayList<String>>Second cut: OverviewWe can eliminate the compound generics by using more than one classpublic class Grammar implements Iterable Map<String, Definition> grammar; // all the rulespublic class Definition List<Rule> definition;public class Rule String lhs; // the definiendum List<String> rhs; // the definiensSecond cut: More detailpublic class Grammar implements Iterable Map<String, Definition> grammar; // rules for all the nonterminals public Grammar() { grammar = new TreeMap<String, Definition>(); } // constructor public void addRule(String rule) throws IllegalArgumentException public Definition getDefinition(String nonterminal) public Iterator iterator() public void print()public class Definition List<Rule> definition; // all definitions for some unspecified nonterminal Definition() // constructor void addRule(Rule rule) Rule getOneRule() public String toString() public class Rule String lhs; // the definiendum List<String> rhs; // the definiens Rule(String text) // constructor public String getLeftHandSide() public List<String> getRightHandSide() public String toString()Second cut: EvaluationAdvantages:Simplifies use of genericsDisadvantages:Many more methodsDefinitions are “unattached” from nonterminal being definedThis makes it easier to parse definitionsSeems a bit unnaturalNeed to pass the tokenizer around as an additional argumentDoesn’t help with the problem that the caller still has to separate out the definiendum from the definiensThird (very brief) cutDefinition and Rule are basically both just lists of stringsWhy not just have them implement List?Methods to implement:public boolean add(Object o)public void
View Full Document
Unlocking...