Parsing unordered sequence with parsing expression grammar

Is there a (simple) way, within a parsing expression grammar (PEG), to express an "unordered sequence"? A rule such as

Rule <- A B C

requires A, B and C to match in order. A rule such as

Rule <- (A B C) / (B C A) / (C A B) / (A C B) / (C B A) / (B A C)

allows them to match in any order (which is what we want) but it is cumbersome and inapplicable in practice with more terms in the sequence.

Is the only solution to use a syntactically looser rule such as

Rule <- (A / B / C){3}

and semantically check that each rule matches only once?

The fact that, e.g., Relax NG Compact Syntax has an "unordered list" operator to parse XML make me hint that there is no obvious solution.

Last question: do you think the addition of such an operator would bring ambiguity to PEG?

-------------Problems Reply------------

Grammar rules express precisely the sequence of forms that you want, regardless of parsing engine (e.g., PEG, LALR, LL(k), ...) that you choose.

The only way to express that you want all possible sequences of just of something using BNF rules is the big ugly rule you proposed.

The standard solution is to simply define:

rule <- (A | B | C)*

(or whatever syntax your parser generator accepts for lists) and semantically count that only 3 forms are provided and they are unique.

Often people building parser generators add special "extended BNF" notations to let them describe special circumstances; you gave an example use {3} as special syntax implying that you only wanted "3 of" under the assumption the parser generator accepts this notation and does the appropriate enforcement. One can imagine an extension notation {unique} to let you describe your situation. I've never seen a parser generator that implemented that idea.

Category:parsing Views:1 Time:2011-07-17

Related post

  • Excluding certain elements from a specified set in Parsing Expressive Grammar (PEG.js)? 2011-02-08

    I am writing a lexer for Haskell using JavaScript and Parsing Expression Grammar, the implementation I use being PEG.js. I have a problem with making it work for reserved words, as demonstrated in a simplified form here: program = ( word / " " )+ wor

  • Are there any Parsing Expression Grammar (PEG) libraries for Javascript or PHP? 2008-09-17

    I find myself drawn to the Parsing Expression Grammar formalism for describing domain specific languages, but so far the implementation code I've found has been written in languages like Java and Haskell that aren't web server friendly in the shared

  • How to use boost::spirit to parse a sequence of words into a vector? 2012-05-02

    I'm trying to learn boost::spirit. As an example, I'm trying to parse a sequence of words into a vector<string>. I tried this: #include <boost/spirit/include/qi.hpp> #include <boost/foreach.hpp> namespace qi = boost::spirit::qi; int

  • Parsing XML files with regular expressions (Perl) 2010-07-30

    I am using regular expression to parse XML file (though regexp is not recommended for xml parsing, but i have to use regexp, no other go). My doubt is how to skip commented lines in XML file, while parsing using Perl. I want Perl to parse XML file, w

  • Parse string into int32 using expressions in C# 2010-10-20

    Basically I've wrote my own parser and I'm parsing a string into and expression and then compiling and storing to be reused later on. For (an odd) example the type of string I'm parsing is this:- if #name == 'max' and #legs > 5 and #ears > 5 th

  • Irony won't parse C# using Irony provided C# grammar 2012-03-10

    So, I'm trying to parse some simple C# code to learn how to use Irony. I'm using the C# grammar included with the Irony samples and using the sample assembly loading code from there as well. There seems to be very little if any documentation on Irony

  • Unable to parse data from an xml file in the Parse Cloud using xmlreader in express app 2014-07-28

    My objective is to get elements of an xml file which i already saved on Parse Cloud for my express app. I started coding after referring this for xmlreader and the guide on Parse httpRequest to retrieve parse file. I tested reading xml elements using

  • Packrat parsing vs. LALR parsing 2010-09-07

    A lot of websites states that packrat parsers can parse input in linear time. So at the first look they me be faster than LALR parser contructed by the tools yacc or bison. I wanted to know if the performance of packrat parsers is better/worse than t

  • ANTLR, Trouble with expression grammar 2011-03-11

    I've recently started using ANTLR. I'm currently trying to encode an expression grammar with +, -, * and array[index] and a few more constructs. This is the desired grammar: Exp -> Exp (+ | - | * | < | &&) Exp | Exp [ Exp ] | -Exp | ( E

  • Recursive Descent Parsing in pascal syntax parser 2011-04-10

    I have got one question about writing recursive descent parsing for checking pascal grammar. I have got this code for example: a := c ; I see that a,c is variables. := and ; - is terminals. This expression I can check. But if I have got smth like thi

  • Make this Expression Grammar unambiguous for LL(1) 2012-02-21

    How can we make this Expression grammar unambiguous for LL(1) parsing? The grammar is very similar to expressions used in most C like languages. Note: Strings in <> are non-terminals, while those in Upper Case are terminals. <expression>

  • why is sax parsing faster than dom parsing ? and how does stax work? 2010-09-29

    somewhat related to: yes, this question is rather long-winded - sorry. I kept is as dense as I felt possible. I bolded the questions to make it easier to peek at before reading the whole th

  • What is the simplest parsing algorithm that can parse C code? 2011-01-24

    Does anyone know what the weakest family of widely-used parsing algorithms is that can parse C code? That is, is the C grammar LL(1), LR(0), LALR(1), etc.? I'm curious because as a side project I'm interested in writing a parser generator for one of

  • I want to generate geopoints after parsing XML using SAX Parser 2010-10-05

    I am able to parse XML using SAX Parser and able to display the points in text view. But now I want the points to be displayed on the map.The XML Contains tags for latitude and longitude. I want to read the latitiudes and longitudes and display them

  • returning meaningful error messages from a parser written with Scala Parser Combinators 2010-12-11

    I try to write a parser in scala using Parser Combinators. If I match recursively, def body: Parser[Body] = ("begin" ~> statementList ) ^^ { case s => { new Body(s); } } def statementList : Parser[List[Statement]] = ("end" ^^ { _ => List() }

  • Is parsing JSON faster than parsing XML 2011-01-04

    I'm creating a sophisticated JavaScript library for working with my company's server side framework. The server side framework encodes its data to a simple XML format. There's no fancy namespacing or anything like that. Ideally I'd like to parse all

  • How can i parse xml using SAX Parser in Android? 2011-06-28

    Hi i want to parse an XML using SAX parser, like i mentioned below. Can any one suggest me to write Handler for this? Thanks in advance Regards Shiva.M --------------Solutions------------- This is perhaps the most detailed answer on XML parsing I hav

  • Parsing html with SAX parser 2011-10-19

    I am trying to parse the normal html file using SAX parser. SAXBuilder builder2 = new SAXBuilder(); try { Document sdoc = (Document); NodeList nl=sdoc.getElementsByTagName("body"); System.out.println("nodelist>>>>

  • Xml Parsing (WSDL format) not parse the data some times? 2011-11-30

    I am using Soap Web services and get response in XML and that Response i am store in NSMutableData and than i perform XML parsing i am using NSXMLParser. my problem is that some times it is works and some times not i can't determine what is the probl

Copyright (C), All Rights Reserved.

processed in 0.091 (s). 11 q(s)