3 ms·

I don't know if it's possible to do the "string describing a set strings" thing that regex does with more powerful parsing while maintaining the ease of use. CF

I don't know if it's possible to do the "string describing a set strings" thing that regex does with more powerful parsing while maintaining the ease of use. CFGs make heavy use of named sub-languages (productions). A regex-style parser would at least have to have some kind of recursion-inducing metacharacter.

YeGoblynQueenne 7y ago
How about this for ease-of-use? sentence --> noun_phrase, verb_phrase. noun_phrase --> det, noun. verb_phrase --> verb, noun_phrase. det --> [the]. det --> [a]. noun --> [cat]. noun --> [bat]. verb --> [eats]. Reads -and behaves- as BNF. Strings in []'s are terminals, the rest are nonterminals. It's directly executable as a logic program (it's Prolog syntactic sugar).
- carapace 7y ago
  And this can be used to generate sentences as well as parse them. ;-)
  - YeGoblynQueenne 7y ago
    Indeed. I tend to forget how counter-intuitive this is. With DCGs you get your recognisers for nothing and your generators for free. As I like to say.
- andrewflnr 7y ago
  That looks great, but it's hard to position it as a regex competitor. I should be more explicit about what I mean by "regex-style": The cool thing about regex that makes them so approachable is that they kind of look like the thing they're describing/matching. Your thing here mostly does not.
  - YeGoblynQueenne 7y ago
    "My thing here" is a grammar so it describes a class of strings. Perhaps this is why it looks to you unlike what it describes? You can make a DCG rule as specific or as general as you like. As a for instance, this is a vim regex I retrieved from my recent history: \[13\/13,15\/12,24-24] You could write this like so in DCG notation: s --> ['[',13,'/',13,,,15,'/',12,,,24,-,24,']']. And that would match the string "[13/13,15/12,24-24]", no less, no more. DCGs are Turing-complete, so you can go all the way from programs to finite automata when you write a pattern to match. They're not really a regex competitor. They were invented in the '70s as a formalism for context-free grammars to be used in representing natural language. They fit right into the logic programming language Prolog that was created soon after (and by some of the same people).
    - andrewflnr 7y ago
      Well, we started this subthread looking for alternatives to regex, so if DCGs aren't in the running I'm not sure what your point is. Also, I happen to believe Turing-completeness is a misfeature for this job.
      - YeGoblynQueenne 7y ago
        The OP asked for "something as easy to use as regular expressions that can processes context-free grammars". You requested ease-of-use. I proposed DCGs. They are not an alternative to regexes in the sense that regexes can't represent anything beyond regular grammars, including CFGs. They can be as simple or as complicated as you want them and they are easy to use. I'm not sure what is a "misfeature". What do you mean? Edit: Apologies if I sound too terse. I'm confused by the terminology of "competitor", "alternative" etc. Are we in some kind of competition to find a technological solution that will take some prize? If so, I'd like to know the rules before I commit to any solution. What exactly are we trying to achieve here?
        andrewflnr 7y ago
        My interpretation of "as easy to use as regular expressions" is that the desired... formalism be usable in the same contexts and with the same casual ease as regex. Think Unix command lines, hairy ad-hoc Python parsing scripts, etc. One of the things that makes regex so well suited to that role is that a string is a regex that matches itself, and you can iteratively add sophistication from there. At the very least, you would want to maintain (or improve, Cthulhu knows there's plenty of room) that incremental quality in any proposed replacement, while increasing its power. It looks like with a DCG, you have to know you're writing one up front, and have to think about what you're parsing at a much more abstract level. The average sysadmin could probably not casually toss one off for a log parsing task. If there's an alternate syntax that gets around that problem, then I'm interested. OTOH... Re "misfeature": one of the cool things about existing parsing formalisms is all the known terminating, mostly (all?) polynomial algorithms for analyzing them. If DCGs are Turing complete, they don't have those algorithms. Turing completeness is not usually a property I want in my parser. That's what I meant by saying it's a misfeature.

YeGoblynQueenne 7y ago

How about this for ease-of-use? sentence --> noun_phrase, verb_phrase. noun_phrase --> det, noun. verb_phrase --> verb, noun_phrase. det --> [the]. det --> [a]. noun --> [cat]. noun --> [bat]. verb --> [eats]. Reads -and behaves- as BNF. Strings in []'s are terminals, the rest are nonterminals. It's directly executable as a logic program (it's Prolog syntactic sugar).

carapace 7y ago
And this can be used to generate sentences as well as parse them. ;-)
- YeGoblynQueenne 7y ago
  Indeed. I tend to forget how counter-intuitive this is. With DCGs you get your recognisers for nothing and your generators for free. As I like to say.
andrewflnr 7y ago
That looks great, but it's hard to position it as a regex competitor. I should be more explicit about what I mean by "regex-style": The cool thing about regex that makes them so approachable is that they kind of look like the thing they're describing/matching. Your thing here mostly does not.
- YeGoblynQueenne 7y ago
  "My thing here" is a grammar so it describes a class of strings. Perhaps this is why it looks to you unlike what it describes? You can make a DCG rule as specific or as general as you like. As a for instance, this is a vim regex I retrieved from my recent history: \[13\/13,15\/12,24-24] You could write this like so in DCG notation: s --> ['[',13,'/',13,,,15,'/',12,,,24,-,24,']']. And that would match the string "[13/13,15/12,24-24]", no less, no more. DCGs are Turing-complete, so you can go all the way from programs to finite automata when you write a pattern to match. They're not really a regex competitor. They were invented in the '70s as a formalism for context-free grammars to be used in representing natural language. They fit right into the logic programming language Prolog that was created soon after (and by some of the same people).
  - andrewflnr 7y ago
    Well, we started this subthread looking for alternatives to regex, so if DCGs aren't in the running I'm not sure what your point is. Also, I happen to believe Turing-completeness is a misfeature for this job.
    - YeGoblynQueenne 7y ago
      The OP asked for "something as easy to use as regular expressions that can processes context-free grammars". You requested ease-of-use. I proposed DCGs. They are not an alternative to regexes in the sense that regexes can't represent anything beyond regular grammars, including CFGs. They can be as simple or as complicated as you want them and they are easy to use. I'm not sure what is a "misfeature". What do you mean? Edit: Apologies if I sound too terse. I'm confused by the terminology of "competitor", "alternative" etc. Are we in some kind of competition to find a technological solution that will take some prize? If so, I'd like to know the rules before I commit to any solution. What exactly are we trying to achieve here?
      - andrewflnr 7y ago
        My interpretation of "as easy to use as regular expressions" is that the desired... formalism be usable in the same contexts and with the same casual ease as regex. Think Unix command lines, hairy ad-hoc Python parsing scripts, etc. One of the things that makes regex so well suited to that role is that a string is a regex that matches itself, and you can iteratively add sophistication from there. At the very least, you would want to maintain (or improve, Cthulhu knows there's plenty of room) that incremental quality in any proposed replacement, while increasing its power. It looks like with a DCG, you have to know you're writing one up front, and have to think about what you're parsing at a much more abstract level. The average sysadmin could probably not casually toss one off for a log parsing task. If there's an alternate syntax that gets around that problem, then I'm interested. OTOH... Re "misfeature": one of the cool things about existing parsing formalisms is all the known terminating, mostly (all?) polynomial algorithms for analyzing them. If DCGs are Turing complete, they don't have those algorithms. Turing completeness is not usually a property I want in my parser. That's what I meant by saying it's a misfeature.