Převod výrazu na AST

Dab

Převod výrazu na AST
« kdy: 27. 09. 2015, 10:39:53 »
V aplikaci pro iOS potřebuju pracovat s AST výrazů. Věci jako "x+1" se pochopitelně hned vyhodnotí. Je nějak možné (v libovolném jazyce použitelném na iOS) zamezit vyhodnocení a dostat místo toho AST? Z toho bych pak mohl jednoduše generovat třeba SQL nebo něco podobného.


gitak

Re:Převod výrazu na AST
« Odpověď #1 kdy: 27. 09. 2015, 10:54:09 »
myslim, ze podminky appstore zakazuji aplikace jazykovych interpretru. mozna je to podobny problem, asi bych sel cestou webove appky a na serveru si muzes delat co chces...

Ivan

Re:Převod výrazu na AST
« Odpověď #2 kdy: 27. 09. 2015, 10:54:42 »
http://www.antlr.org/

Zalezi na tom jaky prohramovaci jazyk potrebujes. Podle potreby to generuje zdrojaky do libovolneho jazyka. (Verze 3 anebo 4).

čumil

Re:Převod výrazu na AST
« Odpověď #3 kdy: 27. 09. 2015, 11:21:24 »
Jak je možné získat AST ze stringu? Jednoduše. Napřed si zadefinuj objekty svého AST. Začni definováním datových typů v AST. Takže ňáké integery a flouty v tvém případě, pak si zadefinuj ňáké výrazy. V tvém případě to bude jen volání funkce (operátoru) a literál (možná i variable acces, kdo ví ...). V argumentech výrazu jsou další výrazy. už vidíš ten strom :D ? A teď parsing. Budeš potřebovat rekurzy. Hodně rekurze. Nevím jestli zvládáš funkcionální programování, ale geniální je knihovna Haskell Parsec. Samozřejmě že ji nevyužiješ, ale princip který využívá můžeš použít i ve svém parseru. Abych schrnul jak funguje. Každý výraz má určitou šablonu, podobu. Parser buď ze stringu výraz vydoluje a nebo vrátí error a vyzkouší se jiná šablona jiného výrazu (když dojdou šablony, hej, asi blbej string ...), a tak pořád dokola až do stack overflow ...

Radek Miček

Re:Převod výrazu na AST
« Odpověď #4 kdy: 27. 09. 2015, 11:51:22 »
Je nějak možné (v libovolném jazyce použitelném na iOS) zamezit vyhodnocení a dostat místo toho AST?

Ano, v některých jazycích to je možné - například C#, F# (v iOS lze provozovat pomocí Xamarin). Dále je to možné v jazycích s makry - například Scala (v iOS lze provozovat pomocí RoboVM). Cíle půjde dosáhnout i v jazycích, kde můžete předefinovat konstrukce, z nichž se skládají výrazy.

Citace
Z toho bych pak mohl jednoduše generovat třeba SQL nebo něco podobného.

Problém ovšem může být ve slově jednoduše - například pro některé výrazy může být poměrně složité vygenerovat SQL.


zboj

  • *****
  • 1 507
    • Zobrazit profil
    • E-mail
Re:Převod výrazu na AST
« Odpověď #5 kdy: 28. 09. 2015, 10:22:38 »
To jde jednoduše v C++ (předefinováním operátorů, jak už tu zaznělo), nicméně pro iOS existuje elegantnější řešení ve Swiftu. Omezíme-li se na sčítání a Double, jde to takto:

Kód: [Vybrat]
protocol Expression {
    func evaluate(vars:[String:Constant]) throws -> Constant
    var string:String { get }
}

extension Expression where Self:CustomStringConvertible {
    var string:String { return description }
}

protocol Constant : Expression {}

extension Constant {
    func evaluate(vars:[String:Constant]) throws -> Constant { return self }
}

extension Double : Expression, Constant {}

enum ExpressionError : ErrorType {
    case FreeVariable
    case UnhandledType
}

struct Variable : Expression {
    let name:String
    init(name:String) { self.name = name }
    func evaluate(vars:[String:Constant]) throws -> Constant {
        if let value = vars[name] { return value }
        else { throw ExpressionError.FreeVariable }
    }
    var string:String { return "$" + name }
}

struct Var {
    static var x:Variable { return Variable(name: "x") }
}

struct PlusExpression : Expression {
    let lhs:Expression
    let rhs:Expression
    init(lhs:Expression, rhs:Expression) { self.lhs = lhs; self.rhs = rhs }
    func evaluate(vars:[String:Constant]) throws -> Constant {
        return try lhs.evaluate(vars) + rhs.evaluate(vars)
    }
    var string:String { return lhs.string + " + " + rhs.string }
}

func +(lhs:Expression, rhs:Expression) -> Expression {
    return PlusExpression(lhs: lhs, rhs: rhs)
}

func +(lhs:Constant, rhs:Constant) throws -> Constant {
    if let x = lhs as? Double {
        if let y = rhs as? Double {
            return x + y
        }
    }
    throw ExpressionError.UnhandledType
}

let expr = Var.x + 5
print(expr.string)
print(try expr.evaluate([ "x": 3 ]))

Triviálně to jde samozřejmě rozšířit na řetězce, komplexní čísla, matice atd.