racket / parser-tools Goto Github PK

I think there might be an issue with the parser generator or at least a missing detail in the documentation. It is not clear how to handle an empty input, the following code shows the issue using a simple lexer and parser definition.

#lang racket

(require parser-tools/lex
         parser-tools/yacc)

(define-tokens tokens (ANY))
(define-empty-tokens empty-tokens (EOF))

(define sample-lexer
  (lexer
   [(eof) (token-EOF)]
   [any-string (token-ANY lexeme)]))

(define sample-parser
  (parser
   [start expr]
   [end EOF]
   [error void]
   [tokens tokens empty-tokens]
   [grammar
    [expr [(ANY) $1]]]))

(define (parse s)
  (define in (open-input-string s))
  (sample-parser (lambda () (sample-lexer in))))

(parse "abc")
(parse "")

The output

"abc"
parser: Cannot continue after error
  context...:
   /snap/racket/current/usr/share/racket/collects/syntax/readerr.rkt:15:2: -raise-read-error
   /snap/racket/current/usr/share/racket/pkgs/parser-tools-lib/parser-tools/yacc.rkt:356:16: parsing-loop
   body of "/home/davide/repos/sample-racket-language/sample.rkt"

The issue is more complex when the parser has multiple end tokens for example

#lang racket

(require parser-tools/lex
         parser-tools/yacc)

(define-tokens tokens (ANY))
(define-empty-tokens empty-tokens (EOF NEWLINE))

(define sample-lexer
  (lexer
   [(eof) (token-EOF)]
   [";" (token-NEWLINE)]
   [(repetition 1 +inf.0 (char-complement ";")) (token-ANY lexeme)]))

(define sample-parser
  (parser
   [start expr]
   [end EOF NEWLINE]
   [error void]
   [tokens tokens empty-tokens]
   [grammar
    [expr [(ANY) $1]]]))


(define in (open-input-string "abc;def"))
(sample-parser (lambda () (sample-lexer in)))
(sample-parser (lambda () (sample-lexer in)))
(sample-parser (lambda () (sample-lexer in)))

The output is

"abc"
"def"
parser: Cannot continue after error
  context...:
   /snap/racket/current/usr/share/racket/collects/syntax/readerr.rkt:15:2: -raise-read-error
   /snap/racket/current/usr/share/racket/pkgs/parser-tools-lib/parser-tools/yacc.rkt:356:16: parsing-loop
   body of "/home/davide/repos/sample-racket-language/sample-2.rkt"

What I would like to achieve is the same behavior of read for example

(define in (open-input-string "1 2"))
(read in)
(read in)
(read in)

Output is

1
2
#<eof>

Is this possible with the parser generator? Am I missing something?

The following file should fail to compile because foo should be unbound. However, foo is bound, to some value internal to the parser:

#lang racket

(require parser-tools/lex parser-tools/cfg-parser)

(define-empty-tokens my-tokens (eof BLAH))

(define x
  (cfg-parser
   (start foo)
   (tokens my-tokens)
   (end eof)
   (grammar
    (foo ((BLAH)
          ;; this should be unbound but it isn't.
          foo)))))

For an example of how this might be harmful, consider:

(define (foo x) ...)
(define my-parser (cfg-parser ... (grammar ... (foo ((bar) (foo $1))))))

Here is a small program that uses an error nonterminal to implement an error recovery rule:

#lang racket/base

(require parser-tools/lex
         parser-tools/yacc)

(define-empty-tokens my-tokens
  [t1 t2 t3 done])

(define (parse lst)
  (define-values [has-next? get-next] (sequence-generate lst))
  ((parser
    (tokens my-tokens)
    (error (λ (a b c) (void)))
    (debug "parser-debug.out")
    (start go)
    (end done)
    (grammar
     [go  [(nt1 nt2 nt3) (list $1 $3)]]
     [nt1 [(t1)          't1]]
     [nt2 [(t2)          't2]
          [(error)       'error]]
     [nt3 [(t3)          't3]]))
   get-next))

(parse '(t1 t2 t3 done))
(parse '(t1 t3 done))

I believe both uses of parse ought to produce the same output, but they do not. The first one succeeds, while the second one fails:

'(t1 t3)
(#(struct:stack-frame 4 #f #f #f) #(struct:stack-frame 0 #f #f #f))
parser: Cannot continue after error

The printed stack says the parser is in state 4, so let’s look at that state in parser-debug.out:

State 4
        nt1 -> t1 . 

        error                                   reduce  3
        t2                                      reduce  3

The error rule is clearly there! Yet it does not fire.

Looking at the source code, the issue appears to be that the code that attempts error states only runs shift rules, not reduce rules:

As far as I can tell, this seems like a simple oversight.

As the title says, I'm getting this error:

application: required keyword argument not supplied
  procedure: ...error-repr.rkt:20:15
  required keyword: #:stack
  arguments...:
   #t
   'b
   #f
   (position 1 1 0)
   (position 2 1 1)
  context...:
   /Applications/Racket v7.7/collects/racket/private/kw.rkt:1551:14
   /Applications/Racket v7.7/share/pkgs/parser-tools-lib/parser-tools/yacc.rkt:347:16: parsing-loop
   "...error-repr.rkt": [running body]
   temp35_0
   for-loop
   run-module-instance!
   perform-require!

Code to reproduce:

#lang racket

(require parser-tools/lex
         parser-tools/yacc)

(define-empty-tokens the-tokens (a b EOF))

(define test-lexer
    (lexer-src-pos
        ["a" 'a]
        ["b" 'b]
        [(eof) 'EOF]))

(define sad-parser
    (parser
        (tokens the-tokens)
        (start q)
        (end EOF)
        (src-pos)
        (error (lambda (invalid-token? token-name token-value start-pos end-pos #:stack s)
                    '()))
        (grammar
            (q [(a) '()]))
    ))

(define (sad-parse input-port)
    (port-count-lines! input-port)
    (sad-parser (lambda () (test-lexer input-port))))

(sad-parse (open-input-string "b"))

I'm hoping I'm just missing something here...it's difficult to debug my parser without the stack information :|

Producing syntax object with the parser is really tedious, due to how one needs to reference appropriate $k-start-pos and $k-end-pos, subtracting positions to get the span, etc.

It would be nice if there is a function/macro adjust-srcloc where:

(adjust-srcloc <syntax-object>)

modifies the syntax object to have the syntax location from $1-start-pos to $n-end-pos

(adjust-srcloc <syntax-object> <k>)

modifies the syntax object to have the syntax location from $k-start-pos to $k-end-pos.

(adjust-srcloc <syntax-object> <a> <b>)

modifies the syntax object to have the syntax location from $a-start-pos to $b-end-pos.

That way, the action expression can be written concisely with:

(adjust-srcloc #`(foo #,(adjust-srcloc #'bar 2)) 1 3)

IIUC, the syntax block for the cfg-parser says that it takes 0 or more clauses, where a clause is any one of those 6 options. It seems that cfg-parser requires at least one clause, and necessarily a grammar clause at that, to even generate valid syntax. Furthermore, I believe the grammar form claims it admits parse rules for 0 or more non-terminals, but the implementation requires at least one parse rule, and I believe that each RHS actually requires one or more grammar-ids, rather than 0 as stated.

See:

*IIUC

This bug was first reported on my fork of parser-tools. As best I could tell, the problem occurs at this location, where this maneuver happens:

#`(grammar (start [() null]
                  [(atok start) (cons $1 $2)])
           (atok [(tok) (make-tok 'tok-id 'tok $e pos ...)] ...)))
#`(start start)

The solution I came up with — well, it passes all tests, I can’t claim to understand why it works — involves renaming some identifiers like so:

(with-syntax ([%start start-id-temp]
              [%atok atok-id-temp])
  #`(grammar (%start [() null]
                     [(%atok %start) (cons $1 $2)])
             (%atok [(tok) (make-tok 'tok-id 'tok $e pos ...)] ...)))
(with-syntax ([%start start-id-temp])
  #`(start %start))

I’d like to contribute a patch but there’s an ugliness I don’t know how to fix:

One can’t literally use %start and %atok as the new identifiers, because then %start and %atok can’t be used as terminals. Hence the use of the variables start-id-temp and atok-id-temp, which hold the temp identifiers. But where to get these identifiers?

“Dude, just use generate-temporary.” Turns out that won’t work. IIUC the parser spawns multiple threads. If these identifiers are different across threads, then the results can’t be recombined. So although the names don’t have to be consistent across every run of the parser, they apparently do have to be consistent among threads.

I have no idea how to make this happen. My so-terrible-it-works idea was to assign very long, very weird names for start-id-temp and atok-id-temp. But I’m not prepared to pollute the Racket codebase with that.