|
Two-level Grammar
A two-level grammar is a formal grammar that is used to generate another formal grammar, such as one with an infinite rule set. This is how a Van Wijngaarden grammar was used to specify Algol 68. A context-free grammar that defines the rules for a second grammar can yield an effectively infinite set of rules for the derived grammar. This makes such two-level grammars more powerful than a single layer of context-free grammar, because generative two-level grammars have actually been shown to be Turing complete. ''Two-level grammar'' can also refer to a formal grammar for a two-level formal language, which is a formal language specified at two levels, for example, the levels of words and sentences. Example A well-known non-context-free language is :\. A two-level grammar for this language is the metagrammar :N ::= 1 , N1 :X ::= a , b together with grammar schema :Start ::= \langle a^N \rangle\langle b^N \rangle\langle a^N \rangle : \langle X^ \rangle ::= \langle X^N \rangle X : ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Formal Grammar
In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the language's syntax. A grammar does not describe the meaning of the strings or what can be done with them in whatever context—only their form. A formal grammar is defined as a set of production rules for such strings in a formal language. Formal language theory, the discipline that studies formal grammars and languages, is a branch of applied mathematics. Its applications are found in theoretical computer science, theoretical linguistics, formal semantics, mathematical logic, and other areas. A formal grammar is a set of rules for rewriting strings, along with a "start symbol" from which rewriting starts. Therefore, a grammar is usually thought of as a language generator. However, it can also sometimes be used as the basis for a "recognizer"—a function in computing that deter ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Van Wijngaarden Grammar
In computer science, a Van Wijngaarden grammar (also vW-grammar or W-grammar) is a two-level grammar which provides a technique to define potentially infinite context-free grammars in a finite number of rules. The formalism was invented by Adriaan van Wijngaarden. to define rigorously some syntactic restrictions which previously had to be formulated in natural language, despite their essentially syntactical content. Typical applications are the treatment of gender and number in natural language syntax and the well-definedness of identifiers in programming languages. For example, "there is one person" and "there are two people" are both grammatically correct but "there are one person" is incorrect for context-sensitive reasons that a W-grammar could represent. The technique was used and developed in the definition of the programming language ALGOL 68. It is an example of the larger class of affix grammars. These grammars continue to be studied. Overview A W-grammar consists of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Algol 68
ALGOL 68 (short for ''Algorithmic Language 1968'') is an imperative programming language that was conceived as a successor to the ALGOL 60 programming language, designed with the goal of a much wider scope of application and more rigorously defined syntax and semantics. The complexity of the language's definition, which runs to several hundred pages filled with non-standard terminology, made compiler implementation difficult and it was said it had "no implementations and no users". This was only partly true; ALGOL 68 did find use in several niche markets, notably in the United Kingdom where it was popular on International Computers Limited (ICL) machines, and in teaching roles. Outside these fields, use was relatively limited. Nevertheless, the contributions of ALGOL 68 to the field of computer science have been deep, wide-ranging and enduring, although many of these contributions were only publicly identified when they had reappeared in subsequently developed programming lang ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Context-free Grammar
In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules are of the form :A\ \to\ \alpha with A a ''single'' nonterminal symbol, and \alpha a string of terminals and/or nonterminals (\alpha can be empty). A formal grammar is "context-free" if its production rules can be applied regardless of the context of a nonterminal. No matter which symbols surround it, the single nonterminal on the left hand side can always be replaced by the right hand side. This is what distinguishes it from a context-sensitive grammar. A formal grammar is essentially a set of production rules that describe all possible strings in a given formal language. Production rules are simple replacements. For example, the first rule in the picture, :\langle\text\rangle \to \langle\text\rangle = \langle\text\rangle ; replaces \langle\text\rangle with \langle\text\rangle = \langle\text\rangle ;. There can be multiple replacement rules for a given nonterminal symbol. The ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Turing Complete
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical computer science, providing a formalisation of the concepts of algorithm and computation with the Turing machine, which can be considered a model of a general-purpose computer. He is widely considered to be the father of theoretical computer science and artificial intelligence. Born in Maida Vale, London, Turing was raised in southern England. He graduated at King's College, Cambridge, with a degree in mathematics. Whilst he was a fellow at Cambridge, he published a proof demonstrating that some purely mathematical yes–no questions can never be answered by computation and defined a Turing machine, and went on to prove that the halting problem for Turing machines is undecidable. In 1938, he obtained his PhD from the Department of Mathemati ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Formal Language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symbols, letters, or tokens that concatenate into strings of the language. Each string concatenated from symbols of this alphabet is called a word, and the words that belong to a particular formal language are sometimes called ''well-formed words'' or ''well-formed formulas''. A formal language is often defined by means of a formal grammar such as a regular grammar or context-free grammar, which consists of its formation rules. In computer science, formal languages are used among others as the basis for defining the grammar of programming languages and formalized versions of subsets of natural languages in which the words of the language represent concepts that are associated with particular meanings or semantics. In computational complexity ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Affix Grammar
An affix grammar is a kind of formal grammar; it is used to describe the Syntax (programming languages), syntax of languages, mainly computer languages, using an approach based on how natural language is typically described.Koster, Cornelis HA.Affix grammars for natural languages" Attribute Grammars, Applications and Systems. Springer, Berlin, Heidelberg, 1991. The grammatical rules of an affix grammar are those of a context-free grammar, except that certain parts in the nonterminals (the affixes) are used as arguments. If the same affix occurs multiple times in a rule, its value must agreement (linguistics), agree, i.e. it must be the same everywhere. In some types of affix grammar, more complex relationships between affix values are possible. Example We can describe an extremely simple fragment of English in the following manner: : ''Sentence'' → ''Subject'' ''Predicate'' : ''Subject'' → ''Noun'' : ''Predicate'' → ''Verb'' ''Object'' : ''Object'' → ''Noun'' : : ''N ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Attribute Grammar
An attribute grammar is a formal way to supplement a formal grammar with semantic information processing. Semantic information is stored in attributes associated with terminal and nonterminal symbols of the grammar. The values of attributes are result of attribute evaluation rules associated with productions of the grammar. Attributes allow to transfer information from anywhere in the abstract syntax tree to anywhere else, in a controlled and formal way. Each semantic function deals with attributes of symbols occurring only in one production rule: both semantic function parameters and its result are attributes of symbols from one particular rule. When a semantic function defines the value of an attribute of the symbol on the left hand side of the rule, the attribute is called ''synthesized''; otherwise it is called ''inherited''. Thus, synthesized attributes serve to pass semantic information up the parse tree, while inherited attributes allow values to be passed from the parent node ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
