Я знаю, что это поздний ответ, но я только что написал крошечный парсер, который позволяет всем операторам (префикс, постфикс и инфикс-левый, инфикс-правый и неассоциативный) иметь произвольный приоритет.
Я собираюсь расширить это для языка с произвольной поддержкой DSL, но я просто хотел отметить, что не нужны пользовательские парсеры для приоритета операторов, можно использовать обобщенный парсер, который не нуждается в таблицах в все, и просто ищет приоритет каждого оператора, как он выглядит. Люди упоминали пользовательские парсеры Pratt или парсинговые парсеры, которые могут принимать недопустимые входные данные - этот не нужно настраивать и (если нет ошибки) не примет неправильный ввод. В некотором смысле он не завершен, он был написан для проверки алгоритма, и его входные данные представлены в форме, которая потребует некоторой предварительной обработки, но есть комментарии, которые проясняют это.
Обратите внимание, что некоторые распространенные типы операторов отсутствуют, например, операторы, используемые для индексации, например таблица [index] или вызов функции функции (выражение-параметра, ...)
Я собираюсь добавить их, но думать о них как о постфиксных операторах, где то, что находится между разделителями '[' и ']' или '(' и ')', анализируется с другим экземпляром синтаксического анализатора выражений. Извините, что пропустил это, но постфиксная часть включена - добавление остальных, вероятно, почти удвоит размер кода.
Поскольку синтаксический анализатор - это всего лишь 100 строк кода ракетки, возможно, я должен просто вставить его сюда, надеюсь, это не дольше, чем позволяет stackoverflow.
Несколько подробностей о произвольных решениях:
Если постфиксный оператор с низким приоритетом конкурирует за те же блоки инфикса, что и префиксный оператор с низким приоритетом, префиксный оператор побеждает. Это не подходит в большинстве языков, так как большинство не имеют постфиксных операторов с низким приоритетом.
- например: ((данные a) (слева 1 +) (до 2 нет) (данные b) (сообщение 3!) (слева 1 +) (данные c))
a + not b! + c, где not - префиксный оператор и! постфиксный оператор и оба имеют более низкий
приоритет чем +, поэтому они хотят сгруппировать несовместимыми способами либо как
(а + не б!) + с
или как
a + (не b! + c)
в этих случаях префиксный оператор всегда побеждает, поэтому вторым является способ синтаксического анализа
Неассоциативные инфиксные операторы действительно существуют, поэтому вам не нужно притворяться, что операторы, которые возвращают разные типы, чем они имеют смысл, имеют смысл вместе, но без разных типов выражений для каждого, это кладжа. Таким образом, в этом алгоритме неассоциативные операторы отказываются ассоциироваться не только с собой, но и с любым оператором с таким же приоритетом. Это распространенный случай, так как <<= ==> = и т. Д. Не ассоциируются друг с другом в большинстве языков.
Вопрос о том, как различные виды операторов (левые, префиксы и т. Д.) Разрывают связи по приоритету, не должен возникать, поскольку на самом деле не имеет смысла предоставлять операторам разных типов одинаковый приоритет. Этот алгоритм что-то делает в таких случаях, но я даже не удосужился выяснить, что именно, потому что такая грамматика - плохая идея.
#lang racket
;cool the algorithm fits in 100 lines!
(define MIN-PREC -10000)
;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp)
;for example "not a*-7+5 < b*b or c >= 4"
;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))"
;is represented as '((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 <)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4))
;higher numbers are higher precedence
;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c))
(struct prec-parse ([data-stack #:mutable #:auto]
[op-stack #:mutable #:auto])
#:auto-value '())
(define (pop-data stacks)
(let [(data (car (prec-parse-data-stack stacks)))]
(set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))
data))
(define (pop-op stacks)
(let [(op (car (prec-parse-op-stack stacks)))]
(set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))
op))
(define (push-data! stacks data)
(set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks))))
(define (push-op! stacks op)
(set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks))))
(define (process-prec min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((>= (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-prec min-prec stacks))))))))
(define (process-nonassoc min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((> (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-nonassoc min-prec stacks))
((= (cadr op) min-prec) (error "multiply applied non-associative operator"))
))))))
(define (apply-op op stacks)
(let [(op-type (car op))]
(cond ((eq? op-type 'post)
(push-data! stacks `(,op ,(pop-data stacks) )))
(else ;assume infix
(let [(tos (pop-data stacks))]
(push-data! stacks `(,op ,(pop-data stacks) ,tos)))))))
(define (finish input min-prec stacks)
(process-prec min-prec stacks)
input
)
(define (post input min-prec stacks)
(if (null? input) (finish input min-prec stacks)
(let* [(cur (car input))
(input-type (car cur))]
(cond ((eq? input-type 'post)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(process-prec (cadr cur)stacks)
(push-data! stacks (cons cur (list (pop-data stacks))))
(post (cdr input) min-prec stacks))))
(else (let [(handle-infix (lambda (proc-fn inc)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(proc-fn (+ inc (cadr cur)) stacks)
(push-op! stacks cur)
(start (cdr input) min-prec stacks)))))]
(cond ((eq? input-type 'left) (handle-infix process-prec 0))
((eq? input-type 'right) (handle-infix process-prec 1))
((eq? input-type 'nonassoc) (handle-infix process-nonassoc 0))
(else error "post op, infix op or end of expression expected here"))))))))
;alters the stacks and returns the input
(define (start input min-prec stacks)
(if (null? input) (error "expression expected")
(let* [(cur (car input))
(input-type (car cur))]
(set! input (cdr input))
;pre could clearly work with new stacks, but could it reuse the current one?
(cond ((eq? input-type 'pre)
(let [(new-stack (prec-parse))]
(set! input (start input (cadr cur) new-stack))
(push-data! stacks
(cons cur (list (pop-data new-stack))))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks)))
((eq? input-type 'data)
(push-data! stacks cur)
(post input min-prec stacks))
((eq? input-type 'grouped)
(let [(new-stack (prec-parse))]
(start (cdr cur) MIN-PREC new-stack)
(push-data! stacks (pop-data new-stack)))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks))
(else (error "bad input"))))))
(define (op-parse input)
(let [(stacks (prec-parse))]
(start input MIN-PREC stacks)
(pop-data stacks)))
(define (main)
(op-parse (read)))
(main)