Проведите различие между оператором «минус» и отрицательными числами в парсере F # lex/yacc

Question

Я пытаюсь проанализировать простой язык скриптов с использованием FsLex и FsYacc, и у меня есть проблема с отличием оператора минус от отрицательных чисел.

Если я оцениваю термин «1 - 2», парсер вернет желаемый АСТ: Minus(NumberLiteral(1.0),NumberLiteral(2.0)). Но если я оцениваю термин «1-2», лексер будет производить номер 1, за которым следует номер -2, что не является допустимым вводом.

Я выполнил минимальную программу для воспроизведения моей проблемы. Аст определяется следующим образом:

module Ast 

type Expression = 
    | NumberLiteral of double 
    | Minus of Expression * Expression 

Код лексер выглядит следующим образом:

{ 
module Lexer 
open Microsoft.FSharp.Text.Lexing 
open Parser 
} 

let whitespace = ' ' 
let digit = ['0' - '9'] 
let number = '-'?digit+ 

rule token = parse 
    | whitespace* { token lexbuf } 
    | '-'   { MINUS } 
    | number  { lexbuf |> LexBuffer<_>.LexemeString |> System.Double.Parse |> NUMBER } 
    | eof   { EOF } 

Анализатор выглядит следующим образом:

%{ 
open Ast 
%} 
%start start 
%token EOF MINUS 
%token <double> NUMBER 
%type <Expression> start 
%% 

start: 
    | expression EOF { $1 } 

expression: 
    | NUMBER   { NumberLiteral $1 } 
    | expression 
     MINUS expression { Minus($1, $3) } 

Моя первая мысль была не обрабатывать - как часть числа в лексере, и пусть синтаксический анализатор определяет, должен ли токен MINUS вызывать минус-оператор или отрицательное число. К сожалению, это также приведет к тому, что ввод «- 2» будет оцениваться как отрицательное число, поскольку пробелы будут потребляться.

Но я предполагаю, что это должна быть общая проблема, и существует общее решение. Итак, как мне лучше справиться с этим?

Answer 1

Обычное решение состоит в том, что -2 на самом деле является выражением. Вы можете «постоянно складывать» - непосредственно оценивать выражения, аргументы которых являются константами - если вы считаете, что было бы слишком неэффективно оценивать -2 (или вы могли бы просто обработать это как особый случай в производстве MINUS expression).