answersLogoWhite

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.

User Avatar

Wiki User

12y ago

What else can I help you with?

Continue Learning about Engineering

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.

Related Questions

What is the difference between context free grammar and regular grammar?

A context-free grammar can generate languages that regular grammars cannot, as it allows for the use of non-terminal symbols in productions. Regular grammars, on the other hand, are less powerful and can only generate regular languages, which are a subset of context-free languages. Context-free grammars are more expressive and have more flexibility in rule definitions compared to regular grammars.


What has the author Anton Nijholt written?

Anton Nijholt has written: 'Context-free grammars' -- subject(s): Formal languages, Parsing (Computer grammar)


What is relation between regular languages finite automaton and regular grammars?

finite automaton is the graphical representation of language and regular grammar is the representation of language in expressions


Context sensitive grammar?

A context-sensitive grammar is a formal grammar type where the production rules are written in the form αAβ → αγβ, where α and β are strings of terminals and nonterminals, A is a nonterminal, and γ is a nonempty string. These grammars are more powerful than context-free grammars and can handle languages that require context to be fully defined. They are often used in linguistic analysis and natural language processing.


What are the examples of transformatinal grammar?

Examples of transformational grammars include Chomsky's phrase structure grammar and tree-adjoining grammar. These grammars employ transformational rules to generate sentences by transforming basic phrase structure trees according to specific syntactic operations. Transformational grammars are used in linguistics to study the underlying structure of language.


What has the author Theodore August Norman written?

Theodore August Norman has written: 'Simultaneous rule application in context-free grammars' -- subject(s): Artificial Languages, Comparative and general Grammar, Grammar, Comparative and general, Languages, Artificial, Programming languages (Electronic computers) 'Discriminant analysis document classification' -- subject(s): Information storage and retrieval systems, Documentation, Automatic indexing, Classification


What has the author V de Fivas written?

V. de Fivas has written: 'New grammar of French grammars..' -- subject(s): French language, Grammar


Is Danish same as swedish?

No. Both languages are from the same family (nordic Germanic languages) but they have different grammars, different vocabularies and different pronunciations. Danish and Norwegian are more simmilar, but also different.


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 significance of Chomsky normal form in the context of formal language theory, particularly in relation to the complexity of generating context-free grammars with 2n-1 rules?

Chomsky normal form is important in formal language theory because it simplifies context-free grammars, making them easier to analyze and work with. By converting a grammar to Chomsky normal form, it becomes more structured and easier to understand. This can help in studying the complexity of generating context-free grammars, especially when dealing with a large number of rules. The formula 2n-1 is significant because it represents the maximum number of rules needed to generate a context-free grammar in Chomsky normal form.


Is German grammar inspired by Latin grammar?

Both German and Latin descended from a common-ancestor language called Proto-Indo-European, which was likely spoken in the steppes of what is today southern Russia and the Ukraine, perhaps 3,000 years ago or more. Both German and Latin are related to dozens of other Indo-European Languages as well (from Irish to Farsi, from Portuguese to Russian, from Hindi to Albanian). Because German and Latin both come from the same source, Indo-European, their grammars are quite a bit more similar to each other than they are to other completely unrelated languages such as Bantu, Chinese, Navajo, or Samoan.To answer your question, then, German grammar is *not* "inspired" by Latin grammar, but instead both Germ and and Latin grammars are closely related and therefor similar to each other.


What is the relationship between s-grammar and automata?

S-grammar and automata are related in the field of theoretical computer science. S-grammar is a formal system used to generate strings in a language, while automata are abstract machines that can recognize patterns in strings. Automata can be used to simulate the behavior of S-grammar, helping to analyze and understand the properties of languages generated by the grammar.