|
Hi Folks, I received this message off-line: Ø
I'd think analytic grammars would be the place to start. Ah! Very exciting. Would you recommend a book on analytic grammars? I just learned a bit about analytic grammars from Wikipedia: Though there is a tremendous body of literature on parsing algorithms, most of these algorithms assume that the language to be parsed is initially described by means of a generative formal grammar, and that the goal is to transform this
generative grammar into a working parser. Strictly speaking, a generative grammar does not in any way correspond to the algorithm used to parse a language, and various algorithms have different restrictions on the form of production rules that are considered
well-formed. An alternative approach is to formalize the language in terms of an analytic grammar in the first place, which more directly corresponds to the structure and semantics of a parser for the language. Examples of analytic grammar formalisms
include the following: - The Language Machine directly implements unrestricted analytic grammars. Substitution rules are used to transform an input to produce outputs and behavior. The system can also produce the lm-diagram which shows what happens when the
rules of an unrestricted analytic grammar are being applied. - Top-down parsing language (TDPL): a highly minimalist analytic grammar formalism developed in the early 1970s to study the behavior of top-down parsers. - Link grammars: a form of analytic grammar designed for linguistics, which derives syntactic structure by examining the positional relationships between pairs of words. - Parsing expression grammars (PEGs): a more recent generalization of TDPL designed around the practical expressiveness needs of programming language and compiler writers. From: Costello, Roger L.
Hi Folks, Would you recommend an algorithm’s book please? Specifically, a book containing algorithms about how to determine if an input (that conforms to a grammar) has property P. Allow me to explain. Suppose I have a grammar for a Book. I could use XSD, or RNG, or Backus-Naur, or EBNF, or something else to express the grammar. Suppose the grammar expresses this: Book must contain a Title, one or more Authors, a Date, an ISBN, and
a Publisher. Many instances are then created. The instances could be expressed in XML, or JSON, or many other ways. Here’s an instance, expressed in XML: <Book> Next, I feed into an algorithm the grammar, an instance, and a property. Here is an example of a property: Does the instance have more than one Author? Here is a graphic which summarizes the situation:
Are there books which describe algorithms for determining if an input (that conforms to a grammar) has a specified property? /Roger |
