Я работаю над книгой по созданию интерпретаторов и в качестве личного проекта я решил реализовать JLox на Go вместо Java, главным образом для изучения Go. В настоящее время я застрял в синтаксическом анализаторе и не знаю, как использовать систему типов для построения грамматики. Есть некоторые подсказки здесь но я хочу использовать типы а-ля Haskell или Rust (возможно я ошибаюсь) .
Пока что это то, что у меня есть:
package ast
import (
"golox/lexer"
)
type Stream interface {
Peek() lexer.Token
Next() lexer.Token
}
type TokenStream []lexer.Token
func (s *TokenStream) Peek() lexer.Token {
return (*s)[0]
}
func (s *TokenStream) Next() lexer.Token {
result := (*s)[0]
*s = (*s)[1:]
return result
}
type NUMBER struct {value float32}
type STRING struct {value string}
type NULL struct {value any}
type BOOL struct {value bool}
func (v NUMBER) Value() float32 {
return v.value
}
func (v STRING) Value() string {
return v.value
}
func (v BOOL) Value() bool {
return v.value
}
func (v NULL) Value() {
}
type Literal interface {
NUMBER | STRING | BOOL | NULL
}
type Expr interface {Literal | Unary | Binary | Grouping}
type Grouping[E Expr] struct {
right lexer.Token
left lexer.Token
expr *E
}
type Unary[E Expr] struct {
operator lexer.Token
expr *E
}
type Binary[E Expr] struct {
operator lexer.Token
left *E
right *E
}
func ParseType(s Stream) (err error) {
switch p:=s.Peek(); p {
}
return
}
Мое намерение состоит в том, чтобы ввести проверку потока токенов, а затем объединить эти токены в виде выражений разных типов. Мой главный вопрос касается типов, которые я определил, поскольку компилятор жалуется, что мои определения недействительны (я думал, что предоставления указателя в качестве поля для рекурсивного типа будет достаточно, но, увы, это не так). Любое понимание ценится! Я знаю, что, вероятно, существует реализация этого языка, но я хотел бы понять эту проблему, прежде чем проверять чужой ответ!
🤔 А знаете ли вы, что...
Go предоставляет богатую стандартную библиотеку.
Ошибка компиляции — invalid recursive type Expr, и это связано с тем, что вы объявляете Expr как набор типов, тип может быть одним из объединений (Литеральный | Унарный | Двоичный | Группировка). Компилятор пытается разрешить E во время компиляции на основе ограничения типа Expr, а также потому, что Expr содержит Grouping, что создает рекурсивную ссылку на тип, что приводит к ошибке.
Я думал, что предоставления указателя в качестве поля для рекурсивного типа будет достаточно, но, увы, это не так.
Вы можете задаться вопросом, почему это работает
type A struct {
a *A
}
это потому, что компилятор точно знает, что такое *A (указатель на A), если не задействованы дженерики, тогда как ограничения рекурсивного типа недействительны, даже если вы используете указатель
В другом языке, таком как Rust, мы можем определить тип перечисления для описания всех возможных выражений:
#[derive(PartialEq, Clone, Debug)]
pub enum Literal {
Bool(bool),
Number(String),
String(String),
Null,
}
#[derive(Debug, PartialEq)]
pub enum Expression {
Litera(Literal),
Grouping(Box<Expression>),
Unary(Token, Box<Expression>),
Binary(Box<Expression>, Token, Box<Expression>),
}
Но поскольку в golang нет перечислимого типа, идиоматический способ его реализации — использование интерфейса.
var (
_ Expr = new(Literal)
_ Expr = new(Grouping)
_ Expr = new(Unary)
_ Expr = new(Binary)
)
type Expr interface {
Evaluate() string
}
type Literal struct {
Value string
}
func (l *Literal) Evaluate() string {
return l.Value
}
type Grouping struct {
Expr Expr
}
func (g *Grouping) Evaluate() string {
if g.Expr == nil {
return ""
} else {
return fmt.Sprintf("(group %s)", g.Expr.Evaluate())
}
}
type Unary struct {
Token *Token
Right Expr
}
func (u *Unary) Evaluate() string {
if u.Right == nil {
return ""
} else {
token := ""
if u.Token != nil {
token = u.Token.Data
}
return fmt.Sprintf("(%s %s)", token, u.Right.Evaluate())
}
}
type Binary struct {
Left Expr
Token *Token
Right Expr
}
type A struct {
a *A
}
func (b *Binary) Evaluate() string {
if b.Left == nil || b.Right == nil || b.Token == nil {
return ""
} else {
return fmt.Sprintf("(%s %s %s)", b.Token.Data, b.Left.Evaluate(), b.Right.Evaluate())
}
}