Just for fun, here's a parsing implementation in J for that problem:
example=:0 :0
0: 4 1 5
1: 2 3 | 3 2
2: 4 4 | 5 5
3: 4 5 | 5 4
4: "a"
5: "b"
ababbb
bababa
abbbab
aaabbb
aaaabbb
)
rule0=: {{ rule4 rule1 rule5 y }}
rule1=: {{ (rule2 rule3 y) or (rule3 rule2 y) }}
rule2=: {{ (rule4 rule4 y) or (rule5 rule5 y) }}
rule3=: {{ (rule4 rule5 y) or (rule5 rule4 y) }}
rule4=: {{ y expect 'a' }}
rule5=: {{ y expect 'b' }}
expect=: {{ if. y={:x do. }:x else. _ end. }}
or=: {{ if. _ e.x do. y else. x end. }}
valid=:{{
messages=: (#~ 'ab' e.~ {.&>) <;._2 y
invalid=: (0 e. rule0)&> messages
(-. invalid)#messages
}}
In this implementation, I imagine the proposed rule8 and rule11 would
look like this:
rule8=:{{ if.0=#y do. _ else. (rule42 y) or rule42 rule8 y end. }}
rule11=:{{ if.0=#y do. _ else. (rule42 rule11 y) or rule42 rule11
rule8 y end. }}
However... it looks like the problem was designed to make
left-to-right parsing more efficient than right-to-left parsing, and
there's several ways to do that. (Probably the most intuitive looking
would be to make the rule implementations be adverbs operating on m
rather than verbs operating on y. And, expect would need to use {. and
}. instead of {: and }:, of course.)
FYI,
--
Raul
On Wed, Dec 30, 2020 at 9:40 AM David Lambert <[email protected]> wrote:
>
> /* file y.y */
> /* $ YACC=bison make y # build */
> /* $ bison y.y && gcc -g -Wall y.tab.c && echo bababa | ./a.out #
> alternative */
> /* $ echo ababbb ./y # use */
>
> %glr-parser
>
> %{
>
> # include<stdio.h>
>
> void yyerror(const char*a) {
> fprintf(stderr, "\n%s\n", a);
> }
>
> int yylex(void) {
> return getchar();
> }
>
> %}
>
> %%
>
> a0: a4 a1 a5 '\n' ;
> a1: a2 a3 | a3 a2 ;
> a2: a4 a4 | a5 a5 ;
> a3: a4 a5 | a5 a4 ;
> a4: 'a' ;
> a5: 'b' ;
>
> %%
>
> int main() {
> return yyparse();
> }
>
>
> #if 0
>
> Given example
>
> 0: 4 1 5
> 1: 2 3 | 3 2
> 2: 4 4 | 5 5
> 3: 4 5 | 5 4
> 4: "a"
> 5: "b"
>
> ababbb
> bababa
> abbbab
> aaabbb
> aaaabbb
>
>
>
> |Date: Tue, 29 Dec 2020 12:43:11 +0000
> |From: "'Mike Day' via Chat" <[email protected]>
> |To: [email protected]
> |Subject: Re: [Jchat] https://adventofcode.com/2020/day/19
> |Message-ID: <[email protected]>
> |Content-Type: text/plain; charset=utf-8
> |
> |This partial copy from (my) part 2 might provide enough insight:
> |<<--- Part Two ---
> |
> |As you look over the list of messages, you realize your matching rules
> aren't quite right. To fix them, completely replace rules 8: 42 and 11: 42
> 31 with the following:
> |
> |8: 42 | 42 8
> |11: 42 31 | 42 11 31
> |This small change has a big impact: now, the rules do contain loops, and
> the list of messages they could hypothetically match is infinite. You'll
> need to determine how these changes affect which messages are valid...... >>
> |
> |So these two rules become self referential.
> |
> |I’ve no Idea what David’s talking about!
> |
> |Cheers,
> |
> |M
>
> #endif
> ----------------------------------------------------------------------
> For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
