3 ms·

could anyone explain the use for this library ?

by bsaul 14y ago

wbhart 14y ago
The major parser libraries that I could find don't allow adding syntax at runtime or to add operators to the expression hierarchy at runtime. Many (though not all) of them also make it difficult to do custom error reporting. These were my major motivations.
- _delirium 14y ago
  Ah right, interesting use-case. I usually think of combinator parsing's advantages versus table-driven parsing (e.g. LALR) being primarily its expressiveness (and amenability to a functional-programming style), but it has a nice runtime-modifiable aspect as well. I wonder how hard it'd be to build a runtime-modifiable table-driven parser, though. Assuming table compilation is fast enough, the most straightforward approach might be to just link in the grammar-compilation code so it's available at runtime, and rebuild the table each time a modification is made. I don't think you'd want to be doing complex incremental surgery on a table-driven parser, but you might not need to.
- alok-g 14y ago
  Doesn't Boost.Spirit [1] allow adding syntax and operators at runtime? (Seriously asking; have never used Spirit) [1] http://boost-spirit.com/home/ http://boost-spirit.com/home/
- _stephan 14y ago
  FParsec's OperatorPrecedenceParser component[1] does support adding (and removing) operators to the expression grammar at runtime. [1] http://www.quanttec.com/fparsec/reference/operatorprecedenceparser.html http://www.quanttec.com/fparsec/reference/operatorprecedence...
- beagle3 14y ago
  Not C .. but are you familiar with Ometa (and its variations, Ometa/JS, Ometa#, PyMeta, etc?) http://tinlizzie.org/ometa/ http://tinlizzie.org/ometa/ It's a turing-complete parser specification language with an interpreter that is very close to being a packrat parser, which embraces adding and extending syntax (in a more general way than your library does, if I understand correctly). Implementing the same idea in C should be possible. I have no idea why you want to add syntax at runtime, but the Ometa model might fit your plans better.
drostie 14y ago
Basically, the general idea of parser combinators is that you want to be able to express your parsing grammar in the sort of high-level description that people actually talk in, not in the low-level description that you get when you are constantly looking at the element string[i] in some switch statement in some function. Here is a simple example: parseAddress = let hexStr2Int = Prelude.read . ("0x" ++) in do start <- many1 hexDigit char '-' end <- many1 hexDigit return $ Address (hexStr2Int start) (hexStr2Int end) (taken from http://therning.org/magnus/archives/289 http://therning.org/magnus/archives/289 .) In actual words, "here is the function for converting a hex string to an integer, now define the variable `start` as the parse of many (or one) hex digits, then there is a hyphen, then the variable `end` is another parse of many (or one) hex digits. Convert `start` and `end` into numbers and put them into an Address object." There are three further blog posts on Haskell+Parsec from the above blog: http://therning.org/magnus/archives/290 http://therning.org/magnus/archives/290 , http://therning.org/magnus/archives/295 http://therning.org/magnus/archives/295 , http://therning.org/magnus/archives/296 http://therning.org/magnus/archives/296 . If you are interested about how such things are generally implemented, this Strange Loop talk is interesting: http://www.infoq.com/presentations/Parser-Combinators http://www.infoq.com/presentations/Parser-Combinators What's probably the most interesting thing to speak of here is simply the fact that it's written in C, rather than in a "normal" functional language. You'll see in the latter presentation for example that there is a sort of "circuit wiring" approach which you can do with Lisp functions, essentially using function calls a(x) in order to describe a directed graph vertex from x to a. I knew that you could pass pointers to functions in C, but I was not aware that it was sophisticated enough to build a parser combinator library, so I might brush up on my rusty C skills to see if I can understand the details of the implementation here.
- dan00 14y ago
  parseAddress = let hexStr2Int = Prelude.read . ("0x" ++) in do start <- many1 hexDigit char '-' end <- many1 hexDigit return $ Address (hexStr2Int start) (hexStr2Int end) Or in applicative style (using attoparsec), which I like a lot more than the monadic style, because you can read it quite literally from the left to the right: parseAddress = Address <$> hexDigits <*> (dash *> hexDigits) where hexDigits = string "0x" *> takeWhile1 hexadecimal dash = char '-'

could anyone explain the use for this library ?

by bsaul 14y ago

could anyone explain the use for this library ?

The major parser libraries that I could find don't allow adding syntax at runtime or to add operators to the expression hierarchy at runtime. Many (though not all) of them also make it difficult to do custom error reporting. These were my major motivations.

_delirium 14y ago
Ah right, interesting use-case. I usually think of combinator parsing's advantages versus table-driven parsing (e.g. LALR) being primarily its expressiveness (and amenability to a functional-programming style), but it has a nice runtime-modifiable aspect as well. I wonder how hard it'd be to build a runtime-modifiable table-driven parser, though. Assuming table compilation is fast enough, the most straightforward approach might be to just link in the grammar-compilation code so it's available at runtime, and rebuild the table each time a modification is made. I don't think you'd want to be doing complex incremental surgery on a table-driven parser, but you might not need to.
alok-g 14y ago
Doesn't Boost.Spirit [1] allow adding syntax and operators at runtime? (Seriously asking; have never used Spirit) [1] http://boost-spirit.com/home/ http://boost-spirit.com/home/
_stephan 14y ago
FParsec's OperatorPrecedenceParser component[1] does support adding (and removing) operators to the expression grammar at runtime. [1] http://www.quanttec.com/fparsec/reference/operatorprecedenceparser.html http://www.quanttec.com/fparsec/reference/operatorprecedence...
beagle3 14y ago
Not C .. but are you familiar with Ometa (and its variations, Ometa/JS, Ometa#, PyMeta, etc?) http://tinlizzie.org/ometa/ http://tinlizzie.org/ometa/ It's a turing-complete parser specification language with an interpreter that is very close to being a packrat parser, which embraces adding and extending syntax (in a more general way than your library does, if I understand correctly). Implementing the same idea in C should be possible. I have no idea why you want to add syntax at runtime, but the Ometa model might fit your plans better.

drostie 14y ago

Basically, the general idea of parser combinators is that you want to be able to express your parsing grammar in the sort of high-level description that people actually talk in, not in the low-level description that you get when you are constantly looking at the element string[i] in some switch statement in some function. Here is a simple example: parseAddress = let hexStr2Int = Prelude.read . ("0x" ++) in do start <- many1 hexDigit char '-' end <- many1 hexDigit return $ Address (hexStr2Int start) (hexStr2Int end) (taken from http://therning.org/magnus/archives/289 http://therning.org/magnus/archives/289 .) In actual words, "here is the function for converting a hex string to an integer, now define the variable `start` as the parse of many (or one) hex digits, then there is a hyphen, then the variable `end` is another parse of many (or one) hex digits. Convert `start` and `end` into numbers and put them into an Address object." There are three further blog posts on Haskell+Parsec from the above blog: http://therning.org/magnus/archives/290 http://therning.org/magnus/archives/290 , http://therning.org/magnus/archives/295 http://therning.org/magnus/archives/295 , http://therning.org/magnus/archives/296 http://therning.org/magnus/archives/296 . If you are interested about how such things are generally implemented, this Strange Loop talk is interesting: http://www.infoq.com/presentations/Parser-Combinators http://www.infoq.com/presentations/Parser-Combinators What's probably the most interesting thing to speak of here is simply the fact that it's written in C, rather than in a "normal" functional language. You'll see in the latter presentation for example that there is a sort of "circuit wiring" approach which you can do with Lisp functions, essentially using function calls a(x) in order to describe a directed graph vertex from x to a. I knew that you could pass pointers to functions in C, but I was not aware that it was sophisticated enough to build a parser combinator library, so I might brush up on my rusty C skills to see if I can understand the details of the implementation here.

dan00 14y ago
parseAddress = let hexStr2Int = Prelude.read . ("0x" ++) in do start <- many1 hexDigit char '-' end <- many1 hexDigit return $ Address (hexStr2Int start) (hexStr2Int end) Or in applicative style (using attoparsec), which I like a lot more than the monadic style, because you can read it quite literally from the left to the right: parseAddress = Address <$> hexDigits <*> (dash *> hexDigits) where hexDigits = string "0x" *> takeWhile1 hexadecimal dash = char '-'