0
Structured or formal grammars are a method of describing a computer language in another meta-language, that if the grammar. For example, you could use EBNF to describe the grammar for the language Pascal. The meta-language, the language in which the grammar is expressed, varies with the tools in use.
Structured grammars are typically used to implement programming languages, but are also commonly used to create parsers for meta-languages such as HTML or XML, for command oriented streams, or for complex protocols (such as HTTP).
This formal grammar definition acts as input to a parser generator. Parser generators are also compiler generators or compiler compilers, but these tools never generate a compiler. Instead, they generate lexical analyzers and parser tools, typically resulting in an abstract syntax tree (semantic node tree) in some form.
A lexical analyzer is the tool that digests the input in the final language (e.g. Pascal), and decides on each fragment (token) what it is: a keyword, a number, etc. The parser generator folds the stream of tokens into semantic nodes (an expression, a variable definition, etc).
At that point, the input (the Pascal program in this example) is known to be syntactically correct. The next stages include semantic analysis (does it make sense and what does it mean?), code generation and code optimization.
The most famous (and infamous) representative is the pair of lex and yacc. Lex generates a lexical analyzer, yacc (short for Yet Another Compiler Compiler) generates a parser. Lex and Yacc's more modern successors are Flex and Bison, other popular tools include ANTLR. Other tools are available.
Still curious? Ask our experts.
Chat with our AI personalities
Professor
Fran
SteveAdd your answer:
Earn +20 pts
What is Chomsky's classification of languages?
I believe it has something to do with the articulatory aspect (as opposed to other's acoustic and perceptual classifications). > No, it is not. This is a hierarchy of formal grammars that rule the production of (human, computer, nature, etc.) "assertions". This approach is focused on a generative view of the meaningful sentences: each one of those could be generated by rules defined by a grammar, or syntactical rules. The classification is ordered by levels of expressiveness and complexity. See the related link on Wikipedia for further information.
What is the use of theory of computation?
In simple words to learn any natural language like ENGLISH, HINDI,FRENCH.... firstly we need to learn the vocabulary and grammar of that language. That means we have to learn how the language is actually specified. In the same way programming languages(formal languages) like C,C++, JAVA.... has their own vocabulary and grammar and such grammar is specified with the help of mathematical model that is called as Theory of Computation.
What is the grammatical rules governing programming languages?
Language consists of a set of strings (syntactically correct programs) of characters from some alphabet of symbols. Grammar -Formal definition of the syntax of the language. -It naturally defines the hierarchical structure of many PL's. Source: My CMSC 124 (Design and Implementation of Programming Languages) Teacher
What is difference between Grammar Translation Method- Direct Method and Audio Lingual Method?
Ah, the Grammar Translation Method focuses on translating between native and target languages, like a beautiful dance between two languages. The Direct Method immerses you in the target language, like taking a peaceful stroll through a linguistic garden. And the Audio Lingual Method uses repetition and audio cues to help you learn, like a gentle melody guiding you through language learning. Each method is like a different brushstroke in the painting of language education, each with its own unique beauty.
Difference between chomsky normal form and greibach normal form?
1,In computer science, a formal grammar is said to be in Chomsky normal form if all of its production rules are of the form: where A, B and C are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and λ is the empty string. Also, neither B nor C may be the start symbol. Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be efficiently transformed into an equivalent one which is in Chomsky normal form. With the exception of the optional rule Sλ (included when the grammar may generate the empty string), all rules of a grammar in Chomsky normal form are expansive; thus, throughout the derivation of a string, each string of terminals and nonterminals is always either the same length or one element longer than the previous such string. The derivation of a string of length n is always exactly 2n − 1 steps long. Furthermore, since all rules deriving nonterminals transform one nonterminal to exactly two nonterminals, a parse tree based on a grammar in Chomsky normal form is a binary tree, and the height of this tree is limited to at most the length of the string. Because of these properties, many proofs in the field of languages and computability make use of the Chomsky normal form. These properties also yield various efficient algorithms based on grammars in Chomsky normal form; for example, the CYK algorithm that decides whether a given string can be generated by a given grammar uses the Chomsky normal form. The Chomsky normal form is named after Noam Chomsky, the US linguist who invented the Chomsky hierarchy. 2,In computer science, to say that a context-free grammar is in Greibach normal form (GNF) means that all production rules are of the form: where A is a nonterminal symbol, α is a terminal symbol, X is a (possibly empty) sequence of nonterminal symbols not including the start symbol, S is the start symbol, and λ is the null string. Observe that the grammar must be without left recursions. Every context-free grammar can be transformed into an equivalent grammar in Greibach normal form. (Some definitions do not consider the second form of rule to be permitted, in which case a context-free grammar that can generate the null string cannot be so transformed.) This can be used to prove that every context-free language can be accepted by a non-deterministic pushdown automaton. Given a grammar in GNF and a derivable string in the grammar with length n, any top-down parser will halt at depth n. Greibach normal form is named after Sheila Greibach.
