41–50 of 74 posts
Consider the most basic parsers you might want. For instance, a parser that only succeeds if it matches a string exactly, a parser that matches any single character and always succeeds, a parser that matches nothing and returns some constant, a parser that always fails. They're all simple and stupid and let's give them names: string("foobar") : Parser char : Parser always (x: A): Parser never : Parser These are parse…
Earlier quoted context omitted.
Hm? I don't see why these would have to be monadic. A simple type Parser t = Input -> Maybe (t, Input) or similar would be enough? Simple function composition gets you the rest of the way. (I grant you, it might be a bit tedious to write parsers this way, and monadic notation certainly makes it more pleasant in most cases.) For anyone following along at home: think function which takes input + current position and ma…
Yeah that type is enough to make a monad. In slightly fancy language the type you just wrote is just StateT Input Maybe. Monadic mostly makes me think of bind which is just about chaining (technically also return is needed, but here return is just always succeed and give that value) and parsers have a natural notion of run one after the other.
Except the newtype -- which was kind of my point :).
Earlier quoted context omitted.
Roughly, context sensitive can be covered by monadic parsers, while applicative parsers are context free. LR(k) also corresponds to context free parsers. So, at least for monadic combinators they are more powerful. I also think they're fairly modular. The primitive parsers are fairly easy to write and once you have a small library (or use an existing one like Parsec) of them it is fairly easy to put them together (in…
Ok, but what about the efficiency of LR(k) parsers implemented using monads? Further, do monads warn the user when there is an ambiguity in the "grammar"?
Monadic parsers can do context-sensitive things that context free parsers can't, but they can't have unordered options which context free parsers can. So really monadic parsers have different powers to context-free.
> do monads warn the user when there is an ambiguity in the "grammar"?
You don't have ambiguity in the grammar because monadic parsers only provide ordered options.
You've linked to my csharp-monad library for C# parser combinators. This has been superseded by my language-ext project: https://github.com/louthy/language-ext/
It is a much more advanced and efficient port of the Haskell Parsec library. Would you mind linking to that instead?
Your Sprache examples would look like this in language-ext:
public static readonly Parser JCLText =
from open in ch('$')
from ws1 in spaces
from command in asString(many(noneOf(' ')))
from ws2 in spaces
from content in asString(many(noneOf('"')))
select new JCLCommand(command, content);
public static readonly Parser GlobalText =
from variablename in asString(many(noneOf('=')))
from ws2 in ch('=')
from openbrack in ch('(')
from filepath in asString(many(noneOf(')')))
from closebrack in ch(')')
select new JCLCommand(variablename, filepath);
static Parser token(Parser p) =>
from x in p
from _ in either(spaces, eof)
select x;
static Parser symbol(string x) =>
token(str(x));
static Parser identifier =
token(asString(many1(alphaNum)));
static Parser quotes(Parser p) =>
between(symbol("\""), symbol("\""), p);
static Parser parens(Parser p) =>
between(symbol("("), symbol(")"), p);
static Parser quoteText =
token(quotes(asString(many(satisfy(x => x != '"')))));
static Parser parensText =
token(parens(asString(many(satisfy(x => x != ')')))));
static readonly Parser JCLText =
from open in symbol("$")
from command in identifier
from content in quoteText
select new JCLCommand(command, content);
static readonly Parser GlobalText =
from variablename in identifier
from ws2 in symbol("=")
from filepath in parensText
select new JCLCommand(variablename, filepath);
static readonly Parser> Commands =
from _ in spaces
from commands in many1(either(JCLText, GlobalText))
select commands;
Consider the most basic parsers you might want. For instance, a parser that only succeeds if it matches a string exactly, a parser that matches any single character and always succeeds, a parser that matches nothing and returns some constant, a parser that always fails. They're all simple and stupid and let's give them names: string("foobar") : Parser char : Parser always (x: A): Parser never : Parser These are parse…
But what is the class of grammar they support? I suspect these combinators are not very powerful compared to e.g. LR(k) parsers, and provide a false sense of modularity. (E.g. a minor grammar change leading to a large scale rewrite).
Context sensitivity as I wrote it here is the most powerful but least optimizable version. There are plenty of tricks to improve optimization. You can even write a "cut" combinatory to break backtracking.
It's a huge design space. The answer to all of your questions will probably be: it depends.
Earlier quoted context omitted.
I didn't really 'get' parser combinators until I watched the following introduction (showing how to build a parser library from scratch in F#): https://skillsmatter.com/skillscasts/9731-understanding-pars... . Highly recommended.
Or watch on youtube: https://www.youtube.com/watch?v=RDalzi7mhdY No need to create an account or login
Earlier quoted context omitted.
Ok, but what about the efficiency of LR(k) parsers implemented using monads? Further, do monads warn the user when there is an ambiguity in the "grammar"?
> monadic combinators are more powerful [than context free parsers] Monadic parsers can do context-sensitive things that context free parsers can't, but they can't have unordered options which context free parsers can. So really monadic parsers have different powers to context-free. > do monads warn the user when there is an ambiguity in the "grammar"? You don't have ambiguity in the grammar because monadic parsers o…
Oh, but you do have ambiguity in the grammar, except that parser returns one of the possible parse trees deterministically and thus doesn't warn you that the input could be parsed differently. This leads to the false impression that your grammar is unambiguous.
Slightly off-topic but please stop this js smooth scroll nonsense. If I wanted to use smooth scroll I would have enabled it in my browser.
Consider the most basic parsers you might want. For instance, a parser that only succeeds if it matches a string exactly, a parser that matches any single character and always succeeds, a parser that matches nothing and returns some constant, a parser that always fails. They're all simple and stupid and let's give them names: string("foobar") : Parser char : Parser always (x: A): Parser never : Parser These are parse…
Consider the most basic parsers you might want. For instance, a parser that only succeeds if it matches a string exactly, a parser that matches any single character and always succeeds, a parser that matches nothing and returns some constant, a parser that always fails. They're all simple and stupid and let's give them names: string("foobar") : Parser char : Parser always (x: A): Parser never : Parser These are parse…
I have the overall feeling that most people don’t realize that parser combinators are nothing more that disguized recursive descent parsers. Personally I love both.