XML.orgXML.org
FOCUS AREAS |XML-DEV |XML.org DAILY NEWSLINK |REGISTRY |RESOURCES |ABOUT
OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.

 


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
RE: Recommend a book on algorithms for determining if an input(that conforms to a grammar) has a specified property?

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.
Sent: Sunday, August 17, 2014 5:18 PM
To: xml-dev@lists.xml.org
Subject: Recommend a book on algorithms for determining if an input (that conforms to a grammar) has a specified property?

 

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>
   
<Title>Introduction to Graph Theory</Title>
   
<Author>Richard J. Trudeau</Author>
   
<Date>1993</Date>
   
<ISBN>0-486-67870-9</ISBN>
   
<Publisher>Dover</Publisher>
</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  



[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS