BNF Syntax.


35 views
Uploaded on:
Description
A linguistic use normally has a
Transcripts
Slide 1

BNF Grammar Example configuration of an information structure

Slide 2

Form of BNF standards <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 characterized here (however you realize what they are) : <letter> , <digit> , <punctuation mark> , <any chars> (any printable nonalphabetic character aside from twofold quote)

Slide 3

Notes on phrasing A linguistic use commonly has a "top level" component A string is a "sentential structure" in the event that it fulfills the punctuation of the top level component A string is a "sentence" on the off chance that it is a sentential frame and is made altogether out of terminals A string "has a place with" a syntax on the off chance that it fulfills the guidelines of that language structure

Slide 4

Uses of a language structure A BNF linguistic use can be utilized as a part of two routes: To produce strings having a place with the linguistic use To do this, begin with a string containing a nonterminal; while there are still nonterminals in the string { supplant a nonterminal with one of its definitions } To perceive strings having a place with the sentence structure This is how projects are ordered - a system is a string having a place with the linguistic use that characterizes the dialect Recognition is much harder than era

Slide 5

Generating sentences I need to compose a project that peruses in a language structure, stores it in some fitting information structure, then creates irregular sentences having a place with that punctuation I have to choose: How to store the sentence structure What operations to give on the linguistic use These choices are entwined! How I store the language structure figures out what operations are simple and proficient (and even conceivable!)

Slide 6

Development approaches Bad approach: Design a general representation for sentence structures and a complete arrangement of operations on them Actually, this is a decent approach in the event that you are composing a broadly useful bundle for general use- - for instance, for incorporation in the Java API Otherwise, it just makes your project a great deal more mind boggling Good approach: Decide the operations you requirement for this system, and outline a representation for syntaxes that backings these operations It\'s a pleasant reward if the configuration can later be stretched out for different purposes Remember the Extreme Programming motto YAGNI: "You ain\'t going to need it."

Slide 7

Requirements and limitations We have to peruse the linguistic use in But we don\'t have to change it later Any apparatuses for building the punctuation structure can be private We have to turn upward the meanings of nonterminals We require this since we should supplant each nonterminal with one of its definitions We have to know the top level component of the sentence structure But we can simply expect that we recognize what it is Really going after, we can demand that the top-level component be <sentence>

Slide 8

First cut open class Grammar executes Iterable List<String> principle;/a solitary option for a nonterminal List<List<String>> definition;/every one of the guidelines for one nonterminal Map<String, List<List<String>>> language structure;/rules for all the nonterminals open Grammar() { linguistic use = new TreeMap<String, List<String>>(); } open void addRule(String standard) tosses IllegalArgumentException open List<List<String>> getDefinition(String nonterminal) open List<String> getOneRule(String nonterminal)/arbitrary decision open iterator() open void print()

Slide 9

First cut: Evaluation Advantages Small, effortlessly learned interface Just one class Can be made to work Disadvantages As planned, <foo> ::= bar | baz is two tenets, requiring two calls to addRule ; henceforth obliges guest to do a portion of the parsing, to isolate out the left-hand side Requires some genuinely confused utilization of generics ArrayList actualizes List (consequently is a List ), however consider: List<List<String>> definition = makeList(); This announcement is legitimate if makeList() gives back an ArrayList<List<String>> It is not lawful if makeList() gives back an ArrayList<ArrayList<String>>

Slide 10

Second cut: Overview We can wipe out the compound generics by utilizing more than one class open class Grammar executes Iterable Map<String, Definition> linguistic use;/every one of the principles open class Definition List<Rule> definition; open class Rule String lhs;/the definiendum List<String> rhs;/the definiens

Slide 11

Second cut: More detail open class Grammar executes Iterable Map<String, Definition> sentence structure;/rules for all the nonterminals open Grammar() { syntax = new TreeMap<String, Definition>(); }/constructor open void addRule(String principle) tosses IllegalArgumentException open Definition getDefinition(String nonterminal) open iterator() open void print() open class Definition List<Rule> definition;/all definitions for some unspecified nonterminal Definition()/constructor void addRule(Rule standard) Rule getOneRule() open String toString() open class Rule String lhs;/the definiendum List<String> rhs;/the definiens Rule(String content)/constructor open String getLeftHandSide() open List<String> getRightHandSide() open String toString()

Slide 12

Second cut: Evaluation Advantages: Simplifies utilization of generics Disadvantages: Many more strategies Definitions are "unattached" from nonterminal being characterized This makes it simpler to parse definitions Seems somewhat unnatural Need to pass the tokenizer around as an extra contention Doesn\'t assist with the issue that the guest still needs to isolate out the definiendum from the definiens

Slide 13

Third (exceptionally short) cut Definition and Rule are essentially both just arrangements of strings Why not simply have them execute List ? Techniques to execute: open boolean add(Object o) open void add(int list, Object component) open boolean addAll(Collection c) open boolean addAll(int list, Collection c) open void clear() open boolean contains(Object o) open boolean containsAll(Collection c) open Object get(int file) open int indexOf(Object o) open boolean isEmpty() open iterator() open int lastIndexOf(Object o) open listIterator() open ListIterator listIterator(int list) open boolean remove(Object o) open Object remove(int list) open boolean removeAll(Collection c) open boolean retainAll(Collection c) open Object set(int record, Object component) open int size() open List subList(int fromIndex, int toIndex) open Object[] toArray() open Object[] toArray(Object[] a)

Slide 14

Fourth cut, not exactly as brief The class AbstractList "gives a skeletal usage of the List interface...the software engineer needs just to amplify this class and give usage to the get(int list) and size() strategies." I attempted this, yet... In the event that I don\'t know how AbstractList is executed, by what method would I be able to compose these strategies? No book or API class that I took a gander at gave any insights I might miss something, yet it would appear that the main thing to do is to take a gander at the source code for some of Java\'s classes (like ArrayList ) to perceive how they do it Doable, however an excessive amount of work!

Slide 15

Letting go of a limitation It is great practice to utilize a more broad class or interface in the event that you needn\'t bother with the administrations of a more particular class In this issue, I need to utilize records, yet I couldn\'t care less whether they are ArrayList s, or LinkedList s, or something else Hence, I for the most part lean toward presentations like List<String> rundown = new ArrayList<String>(); For this situation, nonetheless, attempting to do this fair is by all accounts the reason for a large portion of the issues What happens on the off chance that I simply make all rundowns ArrayList s?

Slide 16

Fifth (and last) cut open class Grammar Map<String, Definitions> language structure;/rules for all the nonterminals open Grammar() { punctuation = new TreeMap<String, Definitions>(); } open void addRule(String standard) tosses IllegalArgumentException open Definitions getDefinitions(String nonterminal) open void print() private void addToGrammar(String lhs, SingleDefinition definition) private static boolean isNonterminal(String s) { return s.startsWith("<"); } open class Definitions broadens ArrayList<SingleDefinition> @Override open String toString() open class SingleDefinition develops ArrayList<String> @Override open String toString()

Slide 17

Explanation I of last BNF API Example: <unsigned integer> ::= <digit> | <unsigned integer> <digit> The above is a principle <unsigned integer> is the definiendum (the thing being characterized) <digit> is a solitary meaning of <unsigned integer> <unsigned integer> <digit> is another single meaning of <unsigned integer> So, There is a SingleDefinition comprising of the ArrayList [ "<digit>" ] Another SingleDefinition comprises of the ArrayList [ "<unsigned integer>", "<digit>" ] A Definitions item is a rundown of single definitions, for this situation: [ "<digit>" ], [ "<unsigned integer>", "<digit>" ] A G

Recommended
View more...