Parser persamaan (ekspresi) dengan diutamakan?

Saya telah mengembangkan parser persamaan menggunakan algoritma tumpukan sederhana yang akan menangani operator biner (+, -, |, &, *, /, dll), operator unary (!), Dan tanda kurung.

Menggunakan metode ini, bagaimanapun, membuat saya memiliki semua yang memiliki prioritas yang sama - itu dievaluasi dari kiri ke kanan terlepas dari operatornya, meskipun prioritas dapat diterapkan menggunakan tanda kurung.

Jadi saat ini "1 + 11 * 5" menghasilkan 60, bukan 56 seperti yang diharapkan.

Meskipun ini cocok untuk proyek saat ini, saya ingin memiliki rutinitas tujuan umum yang dapat saya gunakan untuk proyek selanjutnya.

Diedit untuk kejelasan:

Apa algoritme yang baik untuk mengurai persamaan dengan prioritas?

Saya tertarik pada sesuatu yang sederhana untuk diterapkan dan memahami bahwa saya dapat membuat kode sendiri untuk menghindari masalah lisensi dengan kode yang tersedia.

Tatabahasa:

Saya tidak mengerti pertanyaan tata bahasa - saya telah menulis ini dengan tangan. Cukup sederhana sehingga saya tidak melihat perlunya YACC atau Bison. Saya hanya perlu menghitung string dengan persamaan seperti "2 + 3 * (42/13)".

Bahasa:

Saya melakukan ini di C, tetapi saya tertarik pada algoritme, bukan solusi khusus bahasa. C cukup rendah sehingga mudah untuk dikonversi ke bahasa lain jika diperlukan.

Contoh Kode

Saya memposting kode tes untuk pengurai ekspresi sederhana yang saya bicarakan di atas. Persyaratan proyek diubah dan jadi saya tidak perlu mengoptimalkan kode untuk kinerja atau ruang karena tidak dimasukkan ke dalam proyek. Ini dalam bentuk verbose asli, dan harus mudah dimengerti. Jika saya melakukan sesuatu lebih jauh dengan itu dalam hal prioritas operator, saya mungkin akan memilih peretasan makro karena itu cocok dengan program lainnya dalam kesederhanaan. Jika saya pernah menggunakan ini dalam proyek nyata, saya akan menggunakan parser yang lebih kompak / cepat.

Pertanyaan terkait

Desain cerdas parser matematika?

-Adam

Cara yang sulit

Anda menginginkan parser keturunan rekursif .

Untuk mendapatkan prioritas, Anda perlu berpikir secara rekursif, misalnya, menggunakan string sampel Anda,

1+11*5

untuk melakukan ini secara manual, Anda harus membaca 1, lalu melihat plus dan memulai "sesi" penguraian rekursif baru yang dimulai dengan 11... dan pastikan untuk mengurai 11 * 5ke dalam faktornya sendiri, menghasilkan pohon parse dengan 1 + (11 * 5).

Ini semua terasa sangat menyakitkan bahkan untuk mencoba menjelaskan, terutama dengan ketidakberdayaan yang ditambahkan dari C. Lihat, setelah mengurai 11, jika * sebenarnya adalah +, Anda harus mengabaikan upaya membuat istilah dan sebagai gantinya mengurai 11dirinya sebagai faktor. Kepalaku sudah meledak. Itu mungkin dengan strategi rekursif yang layak, tetapi ada cara yang lebih baik ...

Cara yang mudah (benar)

Jika Anda menggunakan alat GPL seperti Bison, Anda mungkin tidak perlu khawatir tentang masalah perizinan karena kode C yang dihasilkan oleh bison tidak tercakup oleh GPL (IANAL tetapi saya cukup yakin alat GPL tidak memaksa GPL aktif kode / binari yang dihasilkan; misalnya Apple mengkompilasi kode seperti say, Aperture dengan GCC dan mereka menjualnya tanpa harus GPL kode tersebut).

Unduh Bison (atau yang setara, ANTLR, dll.).

Biasanya ada beberapa kode contoh yang bisa Anda gunakan untuk menjalankan bison dan mendapatkan kode C yang Anda inginkan yang mendemonstrasikan empat fungsi kalkulator ini:

http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html

Lihatlah kode yang dihasilkan, dan lihat bahwa ini tidak semudah kedengarannya. Juga, keuntungan menggunakan alat seperti Bison adalah 1) Anda belajar sesuatu (terutama jika Anda membaca buku Naga dan mempelajari tata bahasa), 2) Anda menghindari NIH mencoba menemukan kembali roda. Dengan alat pembuat parser yang sebenarnya, Anda sebenarnya memiliki harapan untuk meningkatkannya nanti, menunjukkan kepada orang lain bahwa Anda tahu bahwa parser adalah domain alat parsing.

Memperbarui:

Orang-orang di sini telah memberikan banyak nasihat yang masuk akal. Satu-satunya peringatan saya agar tidak melewatkan alat parsing atau hanya menggunakan algoritma Shunting Yard atau parser rekursif yang digulung tangan adalah bahwa bahasa mainan kecil ¹ suatu hari nanti dapat berubah menjadi bahasa aktual besar dengan fungsi (sin, cos, log) dan variabel, kondisi dan untuk loop.

Flex / Bison mungkin berlebihan untuk penerjemah kecil dan sederhana, tetapi parser + evaluator dapat menyebabkan masalah saat perubahan perlu dilakukan atau fitur perlu ditambahkan. Situasi Anda akan berbeda dan Anda perlu menggunakan penilaian Anda; hanya saja, jangan menghukum orang lain atas dosa-dosa Anda ^[2] dan membangun alat yang kurang dari cukup.

Alat favorit saya untuk parsing

Alat terbaik di dunia untuk pekerjaan itu adalah pustaka Parsec (untuk pengurai yang layak rekursif) yang hadir dengan bahasa pemrograman Haskell. Ini terlihat sangat mirip dengan BNF , atau seperti alat khusus atau bahasa khusus domain untuk penguraian (kode contoh [3]), tetapi sebenarnya ini hanya pustaka biasa di Haskell, yang berarti bahwa ia mengkompilasi dalam langkah pembuatan yang sama dengan yang lain dari kode Haskell Anda, dan Anda dapat menulis kode Haskell arbitrer dan memanggilnya dalam parser Anda, dan Anda dapat mencampur dan mencocokkan semua pustaka lain dalam kode yang sama . (Ngomong-ngomong, menyematkan bahasa penguraian seperti ini dalam bahasa selain Haskell menghasilkan banyak sintaksis. Saya melakukan ini di C # dan berfungsi dengan cukup baik tetapi tidak begitu cantik dan ringkas.)

Catatan:

1 Richard Stallman berkata, dalam Why you should not use Tcl

Pelajaran utama dari Emacs adalah bahwa bahasa untuk ekstensi tidak boleh hanya menjadi "bahasa ekstensi". Ini harus menjadi bahasa pemrograman yang nyata, dirancang untuk menulis dan memelihara program yang substansial. Karena orang pasti ingin melakukan itu!

[2] Ya, saya selamanya takut menggunakan "bahasa" itu.

Juga perhatikan bahwa ketika saya mengirimkan entri ini, pratinjau benar, tetapi pengurai SO kurang dari cukup memakan tag jangkar dekat saya pada paragraf pertama , membuktikan bahwa parser bukanlah sesuatu yang bisa dianggap enteng karena jika Anda menggunakan regex dan satu kali meretas Anda mungkin akan mendapatkan kesalahan kecil dan halus .

[3] Cuplikan pengurai Haskell menggunakan Parsec: kalkulator empat fungsi yang dilengkapi dengan eksponen, tanda kurung, spasi untuk perkalian, dan konstanta (seperti pi dan e).

aexpr   =   expr `chainl1` toOp
expr    =   optChainl1 term addop (toScalar 0)
term    =   factor `chainl1` mulop
factor  =   sexpr  `chainr1` powop
sexpr   =   parens aexpr
        <|> scalar
        <|> ident

powop   =   sym "^" >>= return . (B Pow)
        <|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))

toOp    =   sym "->" >>= return . (B To)

mulop   =   sym "*" >>= return . (B Mul)
        <|> sym "/" >>= return . (B Div)
        <|> sym "%" >>= return . (B Mod)
        <|>             return . (B Mul)

addop   =   sym "+" >>= return . (B Add) 
        <|> sym "-" >>= return . (B Sub)

scalar = number >>= return . toScalar

ident  = literal >>= return . Lit

parens p = do
             lparen
             result <- p
             rparen
             return result

The algoritma halaman shunting adalah alat yang tepat untuk ini. Wikipedia benar-benar membingungkan tentang ini, tetapi pada dasarnya algoritme berfungsi seperti ini:

Katakanlah, Anda ingin mengevaluasi 1 + 2 * 3 + 4. Secara intuitif, Anda "tahu" bahwa Anda harus melakukan 2 * 3 terlebih dahulu, tetapi bagaimana Anda mendapatkan hasil ini? Kuncinya adalah menyadari bahwa saat Anda memindai string dari kiri ke kanan, Anda akan mengevaluasi operator saat operator yang mengikutinya memiliki prioritas yang lebih rendah (atau sama dengan). Dalam konteks contoh, inilah yang ingin Anda lakukan:

1. Lihatlah: 1 + 2, jangan lakukan apapun.
2. Sekarang lihat 1 + 2 * 3, tetap tidak melakukan apa-apa.
3. Sekarang lihat 1 + 2 * 3 + 4, sekarang Anda tahu bahwa 2 * 3 harus dievaluasi karena operator berikutnya memiliki prioritas yang lebih rendah.

Bagaimana Anda menerapkan ini?

Anda ingin memiliki dua tumpukan, satu untuk nomor, dan satu lagi untuk operator. Anda mendorong angka ke tumpukan setiap saat. Anda membandingkan setiap operator baru dengan yang ada di bagian atas tumpukan, jika yang di atas tumpukan memiliki prioritas lebih tinggi, Anda mengeluarkannya dari tumpukan operator, mengeluarkan operan dari tumpukan nomor, menerapkan operator dan mendorong hasilnya ke tumpukan nomor. Sekarang Anda ulangi perbandingan dengan operator tumpukan atas.

Kembali ke contoh, ini berfungsi seperti ini:

N = [] Operasi = []

• Baca 1. N = [1], Ops = []
• Baca +. N = [1], Ops = [+]
• Baca 2. N = [1 2], Ops = [+]
• Baca *. N = [1 2], Ops = [+ *]
• Baca 3. N = [1 2 3], Ops = [+ *]
• Baca +. N = [1 2 3], Ops = [+ *]
  • Pop 3, 2 dan jalankan 2 *3, dan dorong hasilnya ke N. N = [1 6], Ops = [+]
  • +dibiarkan asosiatif, jadi Anda ingin menghapus 1, 6 juga dan menjalankan +. N = [7], Ops = [].
  • Akhirnya dorong [+] ke tumpukan operator. N = [7], Ops = [+].
• Baca 4. N = [7 4]. Ops = [+].
• Anda kehabisan masukan, jadi Anda ingin mengosongkan tumpukan sekarang. Di mana Anda akan mendapatkan hasil 11.

Nah, itu tidak terlalu sulit, bukan? Dan itu tidak membuat permintaan ke tata bahasa atau generator parser.

http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm

Penjelasan yang sangat bagus tentang pendekatan yang berbeda:

• Pengenalan keturunan rekursif
• Algoritme halaman shunting
• Solusi klasik
• Mendaki diutamakan

Ditulis dengan bahasa yang sederhana dan pseudo-code.

Saya suka 'pendakian prioritas'.

Ada artikel bagus di sini tentang menggabungkan parser keturunan rekursif sederhana dengan penguraian prioritas operator. Jika Anda baru-baru ini menulis parser, bacanya harus sangat menarik dan instruktif.

Dahulu kala, saya membuat algoritme penguraian sendiri, yang tidak dapat saya temukan di buku mana pun tentang penguraian (seperti Buku Naga). Melihat petunjuk ke algoritma Shunting Yard, saya melihat kemiripannya.

Sekitar 2 tahun yang lalu, saya membuat postingan tentang itu, lengkap dengan source code Perl, di http://www.perlmonks.org/?node_id=554516 . Sangat mudah untuk melakukan port ke bahasa lain: implementasi pertama yang saya lakukan adalah di assembler Z80.

Ini ideal untuk penghitungan langsung dengan angka, tetapi Anda bisa menggunakannya untuk menghasilkan pohon parse jika perlu.

Perbarui Karena lebih banyak orang dapat membaca (atau menjalankan) Javascript, saya telah menerapkan ulang parser saya di Javascript, setelah kode diatur ulang. Keseluruhan parser berada di bawah 5k kode Javascript (sekitar 100 baris untuk parser, 15 baris untuk fungsi pembungkus) termasuk pelaporan kesalahan, dan komentar.

Anda dapat menemukan demo langsung di http://users.telenet.be/bartl/expressionParser/expressionParser.html .

// operator table
var ops = {
   '+'  : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } },
   '-'  : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return l-r; } },
   '*'  : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } },
   '/'  : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } },
   '**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } }
};

// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };

// input for parsing
// var r = { string: '123.45+33*8', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
    var startOffset = r.offset;
    var value;
    var m;
    // floating point number
    // example of parsing ("lexing") without aid of regular expressions
    value = 0;
    while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    if(r.string.substr(r.offset, 1) == ".") {
        r.offset++;
        while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
    }
    if(r.offset > startOffset) {  // did that work?
        // OK, so I'm lazy...
        return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
    } else if(r.string.substr(r.offset, 1) == "+") {  // unary plus
        r.offset++;
        return parseVal(r);
    } else if(r.string.substr(r.offset, 1) == "-") {  // unary minus
        r.offset++;
        return negate(parseVal(r));
    } else if(r.string.substr(r.offset, 1) == "(") {  // expression in parens
        r.offset++;   // eat "("
        value = parseExpr(r);
        if(r.string.substr(r.offset, 1) == ")") {
            r.offset++;
            return value;
        }
        r.error = "Parsing error: ')' expected";
        throw 'parseError';
    } else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) {  // variable/constant name        
        // sorry for the regular expression, but I'm too lazy to manually build a varname lexer
        var name = m[0];  // matched string
        r.offset += name.length;
        if(name in vars) return vars[name];  // I know that thing!
        r.error = "Semantic error: unknown variable '" + name + "'";
        throw 'unknownVar';        
    } else {
        if(r.string.length == r.offset) {
            r.error = 'Parsing error at end of string: value expected';
            throw 'valueMissing';
        } else  {
            r.error = "Parsing error: unrecognized value";
            throw 'valueNotParsed';
        }
    }
}

function negate (value) {
    return -value;
}

function parseOp(r) {
    if(r.string.substr(r.offset,2) == '**') {
        r.offset += 2;
        return ops['**'];
    }
    if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
        return ops[r.string.substr(r.offset++, 1)];
    return null;
}

function parseExpr(r) {
    var stack = [{precedence: 0, assoc: 'L'}];
    var op;
    var value = parseVal(r);  // first value on the left
    for(;;){
        op = parseOp(r) || {precedence: 0, assoc: 'L'}; 
        while(op.precedence < stack[stack.length-1].precedence ||
              (op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) {  
            // precedence op is too low, calculate with what we've got on the left, first
            var tos = stack.pop();
            if(!tos.exec) return value;  // end  reached
            // do the calculation ("reduce"), producing a new value
            value = tos.exec(tos.value, value);
        }
        // store on stack and continue parsing ("shift")
        stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
        value = parseVal(r);  // value on the right
    }
}

function parse (string) {   // wrapper
    var r = {string: string, offset: 0};
    try {
        var value = parseExpr(r);
        if(r.offset < r.string.length){
          r.error = 'Syntax error: junk found at offset ' + r.offset;
            throw 'trailingJunk';
        }
        return value;
    } catch(e) {
        alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset));
        return;
    }    
}

Akan membantu jika Anda dapat mendeskripsikan tata bahasa yang saat ini Anda gunakan untuk mengurai. Sepertinya masalahnya mungkin ada di sana!

Edit:

Fakta bahwa Anda tidak memahami pertanyaan tata bahasa dan bahwa 'Anda telah menulis ini dengan tangan' sangat mungkin menjelaskan mengapa Anda mengalami masalah dengan ekspresi bentuk '1 + 11 * 5' (yaitu, dengan prioritas operator) . Googling untuk 'tata bahasa untuk ekspresi aritmatika', misalnya, akan menghasilkan beberapa petunjuk yang bagus. Tata bahasa seperti itu tidak perlu rumit:

<Exp> ::= <Exp> + <Term> |
          <Exp> - <Term> |
          <Term>

<Term> ::= <Term> * <Factor> |
           <Term> / <Factor> |
           <Factor>

<Factor> ::= x | y | ... |
             ( <Exp> ) |
             - <Factor> |
             <Number>

akan melakukan trik tersebut misalnya, dan dapat ditambah secara sepele untuk menangani beberapa ekspresi yang lebih rumit (termasuk fungsi misalnya, atau pangkat, ...).

Saya sarankan Anda melihat utas ini , misalnya.

Hampir semua pengantar tata bahasa / parsing memperlakukan ekspresi aritmatika sebagai contoh.

Perhatikan bahwa menggunakan tata bahasa sama sekali tidak berarti menggunakan alat tertentu ( a la Yacc, Bison, ...). Memang, Anda pasti sudah menggunakan tata bahasa berikut:

<Exp>  :: <Leaf> | <Exp> <Op> <Leaf>

<Op>   :: + | - | * | /

<Leaf> :: <Number> | (<Exp>)

(atau sejenisnya) tanpa menyadarinya!

Pernahkah Anda berpikir untuk menggunakan Boost Spirit ? Ini memungkinkan Anda untuk menulis tata bahasa seperti EBNF di C ++ seperti ini:

group       = '(' >> expression >> ')';
factor      = integer | group;
term        = factor >> *(('*' >> factor) | ('/' >> factor));
expression  = term >> *(('+' >> term) | ('-' >> term));

Saat Anda mengajukan pertanyaan, tidak perlu rekursi apa pun. Jawabannya adalah tiga hal: Notasi Postfix ditambah algoritma Shunting Yard ditambah evaluasi ekspresi Postfix:

1). Notasi postfix = diciptakan untuk menghilangkan kebutuhan akan spesifikasi prioritas eksplisit. Baca lebih lanjut di internet tetapi inilah intinya: ekspresi infix (1 + 2) * 3 sementara mudah bagi manusia untuk membaca dan memproses tidak terlalu efisien untuk komputasi melalui mesin. Apa yang? Aturan sederhana yang mengatakan "tulis ulang ekspresi dengan meng-cache di awal, lalu selalu proses dari kiri ke kanan". Jadi infix (1 + 2) * 3 menjadi postfix 12 + 3 *. POST karena operator ditempatkan selalu SETELAH operan.

2). Mengevaluasi ekspresi postfix. Mudah. Baca angka dari string postfix. Dorong mereka di atas tumpukan sampai seorang operator terlihat. Periksa jenis operator - unary? biner? tersier? Keluarkan operan dari tumpukan sebanyak yang diperlukan untuk mengevaluasi operator ini. Evaluasi. Dorong kembali hasil ke tumpukan! Dan kamu hampir selesai. Terus lakukan hingga tumpukan hanya memiliki satu entri = nilai yang Anda cari.

Ayo lakukan (1 + 2) * 3 yang di postfix adalah "12 + 3 *". Baca angka pertama = 1. Dorong di atas tumpukan. Baca selanjutnya. Nomor = 2. Dorong di atas tumpukan. Baca selanjutnya. Operator. Yang mana? +. Jenis apa? Biner = membutuhkan dua operan. Pop stack dua kali = argright adalah 2 dan argleft adalah 1. 1 + 2 adalah 3. Dorong 3 kembali ke stack. Baca selanjutnya dari string postfix. Ini angka. 3. Dorong. Baca selanjutnya. Operator. Yang mana? *. Jenis apa? Biner = membutuhkan dua angka -> pop stack dua kali. Pertama masuk ke argright, kedua kali ke argleft. Evaluasi operasi - 3 kali 3 adalah 9. Dorong 9 pada tumpukan. Baca karakter postfix selanjutnya. Nol. Akhir masukan. Pop stack onec = itulah jawaban Anda.

3). Shunting Yard digunakan untuk mengubah ekspresi infix manusia (mudah) menjadi ekspresi postfix (juga manusia mudah dibaca setelah beberapa latihan). Mudah dikodekan secara manual. Lihat komentar di atas dan net.

Apakah ada bahasa yang ingin Anda gunakan? ANTLR akan membiarkan Anda melakukan ini dari perspektif Java. Adrian Kuhn memiliki sangat baik Langgan tentang cara menulis tata bahasa dieksekusi di Ruby; sebenarnya, contohnya hampir persis dengan contoh ekspresi aritmatika Anda.

Itu tergantung pada seberapa "umum" yang Anda inginkan.

Jika Anda ingin benar-benar umum seperti dapat mengurai fungsi matematika serta sin (4 + 5) * cos (7 ^ 3), Anda mungkin memerlukan pohon parse.

Di mana, menurut saya implementasi lengkap tidak layak untuk ditempelkan di sini. Saya menyarankan agar Anda melihat salah satu " Buku Naga " yang terkenal .

Tetapi jika Anda hanya menginginkan dukungan prioritas , maka Anda dapat melakukannya dengan terlebih dahulu mengubah ekspresi menjadi bentuk postfix di mana algoritme yang dapat Anda salin dan tempel harus tersedia dari google atau saya rasa Anda dapat mengkodekannya sendiri dengan biner pohon.

Ketika Anda memilikinya dalam bentuk postfix, maka itu sangat mudah sejak saat itu karena Anda sudah memahami bagaimana tumpukan membantu.

Saya akan menyarankan curang dan menggunakan Algoritma Halaman Shunting . Ini adalah cara mudah untuk menulis parser jenis kalkulator sederhana dan lebih diutamakan.

Jika Anda ingin melakukan tokenisasi dengan benar dan memiliki variabel, dll. Yang terlibat maka saya akan melanjutkan dan menulis parser keturunan rekursif seperti yang disarankan oleh orang lain di sini, namun jika Anda hanya memerlukan parser bergaya kalkulator maka algoritme ini harus cukup :-)

Saya menemukan ini di PIClist tentang algoritma Shunting Yard :

Harold menulis:

Saya ingat pernah membaca, dahulu kala, tentang algoritme yang mengubah ekspresi aljabar menjadi RPN untuk evaluasi yang mudah. Setiap nilai infix atau operator atau tanda kurung diwakili oleh gerbong kereta di trek. Satu jenis mobil memisahkan diri ke trek lain dan yang lainnya terus berjalan lurus ke depan. Saya tidak ingat detailnya (jelas!), Tetapi selalu berpikir akan menarik untuk membuat kode. Ini kembali ketika saya sedang menulis 6800 (bukan 68000) kode assembly.

Ini adalah "algoritme halaman shunting" dan itulah yang digunakan sebagian besar pengurai mesin. Lihat artikel tentang parsing di Wikipedia. Cara mudah untuk membuat kode algorythm halaman shunting adalah dengan menggunakan dua tumpukan. Satu adalah tumpukan "dorong" dan yang lainnya adalah tumpukan "kurangi" atau "hasil". Contoh:

pstack = () // kosong rstack = () masukan: 1 + 2 * 3 diutamakan = 10 // pengurangan terendah = 0 // jangan kurangi

start: token '1': isnumber, masukkan pstack (push) token '+': isoperator set precedence = 2 jika diutamakan <before_operator_precedence kemudian dikurangi () // lihat di bawah letakkan '+' di pstack (push) token '2' : isnumber, masukkan pstack (push) token '*': isoperator, setel prioritas = 1, masukkan pstack (push) // periksa diutamakan sebagai // di atas token '3': isnumber, masukkan pstack (push) akhir masukan, perlu untuk mengurangi (tujuan adalah kosong pstack) mengurangi () // selesai

untuk mengurangi, lepaskan elemen dari tumpukan dorong dan masukkan ke dalam tumpukan hasil, selalu tukar 2 item teratas di pstack jika berbentuk 'operator' 'number':

pstack: '1' '+' '2' ' ' '3' rstack: () ... pstack: () rstack: '3' '2' ' ' '1' '+'

jika ekspresinya adalah:

1 * 2 + 3

maka pemicu pengurangan akan menjadi pembacaan token '+' yang memiliki precendece lebih rendah daripada '*' yang sudah didorong, jadi itu akan dilakukan:

pstack: '1' ' ' '2' rstack: () ... pstack: () rstack: '1' '2' ' '

lalu tekan '+' dan kemudian '3' dan akhirnya dikurangi:

pstack: '+' '3' rstack: '1' '2' ' ' ... pstack: () rstack: '1' '2' ' ' '3' '+'

Jadi versi singkatnya adalah: nomor push, saat mendorong operator, periksa prioritas operator sebelumnya. Kalau dulu lebih tinggi dari operator yang akan didorong sekarang, turunkan dulu, lalu dorong operator yang sekarang. Untuk menangani tanda kurung cukup simpan prioritas dari operator 'sebelumnya', dan beri tanda pada pstack yang memberi tahu algorius pengurangan untuk berhenti mengurangi saat menyelesaikan bagian dalam pasangan tanda kurung. Tanda kurung penutup memicu pengurangan seperti halnya akhir masukan, dan juga menghilangkan tanda kurung buka dari pstack, dan mengembalikan prioritas 'operasi sebelumnya' sehingga penguraian dapat dilanjutkan setelah kurung tutup di tempat yang ditinggalkannya. Ini bisa dilakukan dengan rekursi atau tanpa (petunjuk: gunakan tumpukan untuk menyimpan prioritas sebelumnya saat menemukan '(' ...). Versi umum ini adalah dengan menggunakan generator parser yang diimplementasikan algorythm halaman shunting, f.ex. menggunakan yacc atau bison atau taccle (analog tcl dari yacc).

Peter

-Adam

Sumber daya lain untuk penguraian prioritas adalah entri parser prioritas Operator di Wikipedia. Meliputi algoritme shunting yard Dijkstra, dan algoritme alternatif pohon, tetapi yang lebih khusus mencakup algoritme pengganti makro yang sangat sederhana yang dapat diimplementasikan dengan mudah di depan pengurai mengabaikan prioritas apa pun:

#include <stdio.h>
int main(int argc, char *argv[]){
  printf("((((");
  for(int i=1;i!=argc;i++){
    if(argv[i] && !argv[i][1]){
      switch(argv[i]){
      case '^': printf(")^("); continue;
      case '*': printf("))*(("); continue;
      case '/': printf("))/(("); continue;
      case '+': printf(")))+((("); continue;
      case '-': printf(")))-((("); continue;
      }
    }
    printf("%s", argv[i]);
  }
  printf("))))\n");
  return 0;
}

Panggil sebagai:

$ cc -o parenthesise parenthesise.c
$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))

Yang mengagumkan dalam kesederhanaannya, dan sangat bisa dimengerti.

Saya telah memposting sumber untuk Penilai Matematika Java ultra kompak (1 kelas, <10 KiB) di situs web saya. Ini adalah pengurai keturunan rekursif dari jenis yang menyebabkan ledakan tengkorak untuk poster jawaban yang diterima.

Ini mendukung prioritas penuh, tanda kurung, variabel bernama dan fungsi argumen tunggal.

saya merilis pengurai ekspresi berdasarkan algoritma Dijkstra's Shunting Yard , di bawah persyaratan Lisensi Apache 2.0 :

http://projects.congrace.de/exp4j/index.html

Saya telah mengimplementasikan parser keturunan rekursif di Java dalam proyek MathEclipse Parser . Ini juga dapat digunakan sebagai modul Google Web Toolkit

Saat ini saya mengerjakan serangkaian artikel yang membangun pengurai ekspresi reguler sebagai alat pembelajaran untuk pola desain dan program yang dapat dibaca. Anda dapat melihat kode yang dapat dibaca . Artikel ini menyajikan penggunaan yang jelas dari algoritma yard shunting.

Saya menulis pengurai ekspresi di F # dan menulis blog tentang itu di sini . Ini menggunakan algoritma halaman shunting, tetapi alih-alih mengubah dari infix ke RPN, saya menambahkan tumpukan kedua untuk mengakumulasi hasil perhitungan. Ini menangani prioritas operator dengan benar, tetapi tidak mendukung operator unary. Saya menulis ini untuk mempelajari F #, bukan untuk mempelajari penguraian ekspresi.

Solusi Python menggunakan pyparsing dapat ditemukan di sini . Parsing notasi infix dengan berbagai operator dengan prioritas cukup umum, dan pyparsing juga mencakup pembangun ekspresi infixNotation(sebelumnya operatorPrecedence). Dengan itu Anda dapat dengan mudah mendefinisikan ekspresi boolean menggunakan "AND", "OR", "NOT", misalnya. Atau Anda dapat memperluas aritmatika empat fungsi Anda untuk menggunakan operator lain, seperti! untuk faktorial, atau '%' untuk modulus, atau tambahkan operator P dan C untuk menghitung permutasi dan kombinasi. Anda bisa menulis parser infix untuk notasi matriks, yang mencakup penanganan operator '-1' atau 'T' (untuk inversi dan transpos). Contoh operatorPrecedence dari parser 4 fungsi (dengan '!'.

Saya tahu ini adalah jawaban yang terlambat, tetapi saya baru saja menulis parser kecil yang memungkinkan semua operator (awalan, postfix dan infix-left, infix-right dan nonassociative) memiliki prioritas yang sewenang-wenang.

Saya akan mengembangkan ini untuk bahasa dengan dukungan DSL sewenang-wenang, tetapi saya hanya ingin menunjukkan bahwa seseorang tidak memerlukan parser khusus untuk prioritas operator, seseorang dapat menggunakan parser umum yang tidak memerlukan tabel sama sekali, dan hanya mencari prioritas setiap operator seperti yang terlihat. Orang-orang telah menyebutkan pengurai Pratt khusus atau pengurai halaman shunting yang dapat menerima masukan ilegal - yang ini tidak perlu disesuaikan dan (kecuali ada bug) tidak akan menerima masukan yang buruk. Dalam arti tertentu, ini tidak lengkap, itu ditulis untuk menguji algoritme dan masukannya dalam bentuk yang memerlukan beberapa pemrosesan awal, tetapi ada komentar yang membuatnya jelas.

Perhatikan beberapa jenis operator yang umum hilang misalnya jenis operator yang digunakan untuk mengindeks yaitu tabel [indeks] atau memanggil fungsi fungsi (parameter-ekspresi, ...) Saya akan menambahkannya, tetapi anggap keduanya sebagai postfix operator di mana apa yang muncul di antara pembatas '[' dan ']' atau '(' dan ')' diuraikan dengan contoh pengurai ekspresi yang berbeda. Maaf telah mengabaikannya, tetapi bagian postfix ada - menambahkan sisanya mungkin akan hampir menggandakan ukuran kode.

Karena parser hanya 100 baris kode raket, mungkin saya harus menempelkannya di sini, saya harap ini tidak lebih lama dari yang diizinkan oleh stackoverflow.

Beberapa detail tentang keputusan sewenang-wenang:

Jika operator postfix prioritas rendah bersaing untuk blok infiks yang sama sebagai operator awalan prioritas rendah, operator awalan menang. Ini tidak muncul di sebagian besar bahasa karena kebanyakan tidak memiliki operator postfix dengan prioritas rendah. - misalnya: ((data a) (left 1 +) (pre 2 not) (data b) (post 3!) (left 1 +) (data c)) adalah a + bukan b! + c dimana tidak adalah a operator awalan dan! adalah operator postfix dan keduanya memiliki prioritas lebih rendah dari + sehingga mereka ingin mengelompokkan dengan cara yang tidak kompatibel baik sebagai (a + bukan b!) + c atau sebagai + (bukan b! + c) dalam kasus ini operator awalan selalu menang, sehingga kedua adalah cara mengurai

Operator infix non-asosiatif benar-benar ada sehingga Anda tidak perlu berpura-pura bahwa operator yang mengembalikan tipe berbeda dari yang mereka anggap masuk akal, tetapi tanpa memiliki tipe ekspresi yang berbeda untuk masing-masing itu adalah kludge. Dengan demikian, dalam algoritme ini, operator non-asosiatif menolak untuk mengasosiasikan tidak hanya dengan diri mereka sendiri tetapi juga dengan operator apa pun dengan prioritas yang sama. Itu adalah kasus umum karena <<= ==> = etc tidak terkait satu sama lain dalam banyak bahasa.

Pertanyaan tentang bagaimana jenis operator yang berbeda (kiri, awalan, dll) memutuskan hubungan pada prioritas adalah pertanyaan yang seharusnya tidak muncul, karena tidak masuk akal untuk memberi operator dari jenis yang berbeda prioritas yang sama. Algoritme ini melakukan sesuatu dalam kasus-kasus itu, tetapi saya bahkan tidak repot-repot mencari tahu dengan tepat apa karena tata bahasa seperti itu adalah ide yang buruk sejak awal.

#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)

Berikut adalah solusi rekursif kasus sederhana yang ditulis dalam Java. Perhatikan bahwa ini tidak menangani angka negatif tetapi Anda dapat menambahkannya jika Anda ingin:

public class ExpressionParser {

public double eval(String exp){
    int bracketCounter = 0;
    int operatorIndex = -1;

    for(int i=0; i<exp.length(); i++){
        char c = exp.charAt(i);
        if(c == '(') bracketCounter++;
        else if(c == ')') bracketCounter--;
        else if((c == '+' || c == '-') && bracketCounter == 0){
            operatorIndex = i;
            break;
        }
        else if((c == '*' || c == '/') && bracketCounter == 0 && operatorIndex < 0){
            operatorIndex = i;
        }
    }
    if(operatorIndex < 0){
        exp = exp.trim();
        if(exp.charAt(0) == '(' && exp.charAt(exp.length()-1) == ')')
            return eval(exp.substring(1, exp.length()-1));
        else
            return Double.parseDouble(exp);
    }
    else{
        switch(exp.charAt(operatorIndex)){
            case '+':
                return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));
            case '-':
                return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));
            case '*':
                return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));
            case '/':
                return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));
        }
    }
    return 0;
}

}

Algoritma dapat dengan mudah dikodekan dalam C sebagai pengurai keturunan rekursif.

#include <stdio.h>
#include <ctype.h>

/*
 *  expression -> sum
 *  sum -> product | product "+" sum
 *  product -> term | term "*" product
 *  term -> number | expression
 *  number -> [0..9]+
 */

typedef struct {
    int value;
    const char* context;
} expression_t;

expression_t expression(int value, const char* context) {
    return (expression_t) { value, context };
}

/* begin: parsers */

expression_t eval_expression(const char* symbols);

expression_t eval_number(const char* symbols) {
    // number -> [0..9]+
    double number = 0;        
    while (isdigit(*symbols)) {
        number = 10 * number + (*symbols - '0');
        symbols++;
    }
    return expression(number, symbols);
}

expression_t eval_term(const char* symbols) {
    // term -> number | expression
    expression_t number = eval_number(symbols);
    return number.context != symbols ? number : eval_expression(symbols);
}

expression_t eval_product(const char* symbols) {
    // product -> term | term "*" product
    expression_t term = eval_term(symbols);
    if (*term.context != '*')
        return term;

    expression_t product = eval_product(term.context + 1);
    return expression(term.value * product.value, product.context);
}

expression_t eval_sum(const char* symbols) {
    // sum -> product | product "+" sum
    expression_t product = eval_product(symbols);
    if (*product.context != '+')
        return product;

    expression_t sum = eval_sum(product.context + 1);
    return expression(product.value + sum.value, sum.context);
}

expression_t eval_expression(const char* symbols) {
    // expression -> sum
    return eval_sum(symbols);
}

/* end: parsers */

int main() {
    const char* expression = "1+11*5";
    printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value);

    return 0;
}

_{libs berikutnya mungkin berguna: yupana - operasi aritmatika yang ketat; tinyexpr - operasi aritmatika + fungsi matematika C + yang disediakan oleh pengguna; mpc - kombinator parser}

Penjelasan

Mari kita tangkap urutan simbol yang mewakili ekspresi aljabar. Yang pertama adalah angka, yaitu digit desimal yang diulang satu kali atau lebih. _{Kami akan merujuk notasi seperti itu sebagai aturan produksi.}

number -> [0..9]+

Operator penjumlahan dengan operannya adalah aturan lain. Ini adalah salah satu numberatau simbol apa pun yang mewakili sum "*" sumurutan.

sum -> number | sum "+" sum

Coba gantikan numberdengan sum "+" sumyang nantinya number "+" numberbisa diperluas menjadi [0..9]+ "+" [0..9]+yang akhirnya bisa direduksi menjadi 1+8ekspresi penjumlahan yang benar.

Substitusi lain juga akan menghasilkan ekspresi yang benar: sum "+" sum-> number "+" sum-> number "+" sum "+" sum-> number "+" sum "+" number-> number "+" number "+" number->12+3+5

Sedikit demi sedikit kita bisa menyerupai seperangkat aturan produksi _{alias tata bahasa} yang mengekspresikan semua kemungkinan ekspresi aljabar.

expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+                                                                    

Untuk mengontrol prioritas operator mengubah posisi aturan produksinya terhadap yang lain. Perhatikan tata bahasa di atas dan perhatikan bahwa aturan produksi untuk *ditempatkan di bawah +ini akan memaksa productevaluasi sebelumnya sum. Implementasi hanya menggabungkan pengenalan pola dengan evaluasi dan dengan demikian mencerminkan aturan produksi.

expression_t eval_product(const char* symbols) {
    // product -> term | term "*" product
    expression_t term = eval_term(symbols);
    if (*term.context != '*')
        return term;

    expression_t product = eval_product(term.context + 1);
    return expression(term.value * product.value, product.context);
}

Di sini kita mengevaluasi termterlebih dahulu dan mengembalikannya jika tidak ada *karakter setelah itu _{pilihan kiri dalam aturan produksi kita} sebaliknya - mengevaluasi simbol setelah dan mengembalikan term.value * product.value _{ini adalah pilihan yang benar dalam aturan produksi kita yaituterm "*" product}