我在哪里可以找到一个_simple_，易于理解的实施LR（1）语法分析器发电机？ [英] Where can I find a _simple_, easy to understand implementation of an LR(1) parser generator?

问题描述

我在哪里可以找到一个简单的（尽可能多的，而不是简单！）实现的LR（1）语法分析器发电机？

Where can I find a simple (as much as possible, but no simpler!) implementation of an LR(1) parser generator?

我不是在寻找性能，只是生成LR（1）状态（项集）。结果
C ++，C＃，Java的能力，和Python都会为我工作。

I'm not looking for performance, just the ability to generate the LR(1) states (item sets).
C++, C#, Java, and Python would all work for me.

推荐答案

我已经写了一个非常简单的C＃和想在这里分享。

I've written a very simple one in C# and wanted to share it here.

它基本上填充动作查找表，它告诉你转向哪个国家或哪个规则使用。减少结果
如果数字非负，那么它表示一个新的状态;如果是否定的，那么它的补（即〜X ）表示规则索引。

It basically populates the action lookup table, which tells you which state to shift to or which rule to use for reduction.
If the number is nonnegative, then it denotes a new state; if it's negative, then its one's complement (i.e. ~x) denotes the rule index.

你现在需要的，是让词法分析器和做的动作表实际的解析

All you need now is to make a lexer and to do the actual parsing with the action table.

注意1：这可能是在生成状态很慢对于现实世界的语法，所以你可能要在生产代码中使用它之前要三思而后行。

Note 1: It might be quite slow at generating the states for a real-world grammar, so you might want to think twice before using it in production code!

注意2：您可能想。仔细检查它的正确性，因为我只检查了一点

Note 2: You might want to double-check its correctness, since I've only checked it a bit.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using size_t = System.UInt32;

public class LRParser
{
    private string[] symbols;  // index => symbol
    private IDictionary<string, size_t> interned = new SortedDictionary<string, size_t>();  // symbol => index
    private int[/*state*/, /*lookahead*/] actions;  // If >= 0, represents new state after shift. If < 0, represents one's complement (i.e. ~x) of reduction rule.

    public LRParser(params KeyValuePair<string, string[]>[] grammar)
    {
        this.interned.Add(string.Empty, new size_t());
        foreach (var rule in grammar)
        {
            if (!this.interned.ContainsKey(rule.Key))
            { this.interned.Add(rule.Key, (size_t)this.interned.Count); }
            foreach (var symbol in rule.Value)
            {
                if (!this.interned.ContainsKey(symbol))
                { this.interned.Add(symbol, (size_t)this.interned.Count); }
            }
        }
        this.symbols = this.interned.ToArray().OrderBy(p => p.Value).Select(p => p.Key).ToArray();
        var syntax = Array.ConvertAll(grammar, r => new KeyValuePair<size_t, size_t[]>(this.interned[r.Key], Array.ConvertAll(r.Value, s => this.interned[s])));
        var nonterminals = Array.ConvertAll(this.symbols, s => new List<size_t>());
        for (size_t i = 0; i < syntax.Length; i++) { nonterminals[syntax[i].Key].Add(i); }

        var firsts = Array.ConvertAll(Enumerable.Range(0, this.symbols.Length).ToArray(), s => nonterminals[s].Count > 0 ? new HashSet<size_t>() : new HashSet<size_t>() { (size_t)s });

        int old;
        do
        {
            old = firsts.Select(l => l.Count).Sum();
            foreach (var rule in syntax)
            {
                foreach (var i in First(rule.Value, firsts))
                { firsts[rule.Key].Add(i); }
            }
        } while (old < firsts.Select(l => l.Count).Sum());

        var actions = new Dictionary<int, IDictionary<size_t, IList<int>>>();
        var states = new Dictionary<HashSet<Item>, int>(HashSet<Item>.CreateSetComparer());
        var todo = new Stack<HashSet<Item>>();
        var root = new Item(0, 0, new size_t());
        todo.Push(new HashSet<Item>());
        Closure(root, todo.Peek(), firsts, syntax, nonterminals);
        states.Add(new HashSet<Item>(todo.Peek()), states.Count);
        while (todo.Count > 0)
        {
            var set = todo.Pop();
            var closure = new HashSet<Item>();
            foreach (var item in set)
            { Closure(item, closure, firsts, syntax, nonterminals); }
            var grouped = Array.ConvertAll(this.symbols, _ => new HashSet<Item>());
            foreach (var item in closure)
            {
                if (item.Symbol >= syntax[item.Rule].Value.Length)
                {
                    IDictionary<size_t, IList<int>> map;
                    if (!actions.TryGetValue(states[set], out map))
                    { actions[states[set]] = map = new Dictionary<size_t, IList<int>>(); }
                    IList<int> list;
                    if (!map.TryGetValue(item.Lookahead, out list))
                    { map[item.Lookahead] = list = new List<int>(); }
                    list.Add(~(int)item.Rule);
                    continue;
                }
                var next = item;
                next.Symbol++;
                grouped[syntax[item.Rule].Value[item.Symbol]].Add(next);
            }
            for (size_t symbol = 0; symbol < grouped.Length; symbol++)
            {
                var g = new HashSet<Item>();
                foreach (var item in grouped[symbol])
                { Closure(item, g, firsts, syntax, nonterminals); }
                if (g.Count > 0)
                {
                    int state;
                    if (!states.TryGetValue(g, out state))
                    {
                        state = states.Count;
                        states.Add(g, state);
                        todo.Push(g);
                    }

                    IDictionary<size_t, IList<int>> map;
                    if (!actions.TryGetValue(states[set], out map))
                    { actions[states[set]] = map = new Dictionary<size_t, IList<int>>(); }
                    IList<int> list;
                    if (!map.TryGetValue(symbol, out list))
                    { map[symbol] = list = new List<int>(); }

                    list.Add(state);
                }
            }
        }

        this.actions = new int[states.Count, this.symbols.Length];
        for (int i = 0; i < this.actions.GetLength(0); i++)
        {
            for (int j = 0; j < this.actions.GetLength(1); j++)
            { this.actions[i, j] = int.MinValue; }
        }
        foreach (var p in actions)
        {
            foreach (var q in p.Value)
            { this.actions[p.Key, q.Key] = q.Value.Single(); }
        }

        foreach (var state in states.OrderBy(p => p.Value))
        {
            Console.WriteLine("State {0}:", state.Value);
            foreach (var item in state.Key.OrderBy(i => i.Rule).ThenBy(i => i.Symbol).ThenBy(i => i.Lookahead))
            {
                Console.WriteLine(
                    "\t{0}: {1} \xB7 {2} | {3} →  {0}",
                    this.symbols[syntax[item.Rule].Key],
                    string.Join(" ", syntax[item.Rule].Value.Take((int)item.Symbol).Select(s => this.symbols[s]).ToArray()),
                    string.Join(" ", syntax[item.Rule].Value.Skip((int)item.Symbol).Select(s => this.symbols[s]).ToArray()),
                    this.symbols[item.Lookahead] == string.Empty ? "\x04" : this.symbols[item.Lookahead],
                    string.Join(
                        ", ",
                        Array.ConvertAll(
                            actions[state.Value][item.Symbol < syntax[item.Rule].Value.Length ? syntax[item.Rule].Value[item.Symbol] : item.Lookahead].ToArray(),
                            a => a >= 0 ? string.Format("state {0}", a) : string.Format("{0} (rule {1})", this.symbols[syntax[~a].Key], ~a))));
            }
            Console.WriteLine();
        }
    }

    private static void Closure(Item item, HashSet<Item> closure /*output*/, HashSet<size_t>[] firsts, KeyValuePair<size_t, size_t[]>[] syntax, IList<size_t>[] nonterminals)
    {
        if (closure.Add(item) && item.Symbol >= syntax[item.Rule].Value.Length)
        {
            foreach (var r in nonterminals[syntax[item.Rule].Value[item.Symbol]])
            {
                foreach (var i in First(syntax[item.Rule].Value.Skip((int)(item.Symbol + 1)), firsts))
                { Closure(new Item(r, 0, i == new size_t() ? item.Lookahead : i), closure, firsts, syntax, nonterminals); }
            }
        }
    }

    private struct Item : IEquatable<Item>
    {
        public size_t Rule;
        public size_t Symbol;
        public size_t Lookahead;

        public Item(size_t rule, size_t symbol, size_t lookahead)
        {
            this.Rule = rule;
            this.Symbol = symbol;
            this.Lookahead = lookahead;
        }

        public override bool Equals(object obj) { return obj is Item && this.Equals((Item)obj); }

        public bool Equals(Item other)
        { return this.Rule == other.Rule && this.Symbol == other.Symbol && this.Lookahead == other.Lookahead; }

        public override int GetHashCode()
        { return this.Rule.GetHashCode() ^ this.Symbol.GetHashCode() ^ this.Lookahead.GetHashCode(); }
    }

    private static IEnumerable<size_t> First(IEnumerable<size_t> symbols, IEnumerable<size_t>[] map)
    {
        foreach (var symbol in symbols)
        {
            bool epsilon = false;
            foreach (var s in map[symbol])
            {
                if (s == new size_t()) { epsilon = true; }
                else { yield return s; }
            }
            if (!epsilon) { yield break; }
        }
        yield return new size_t();
    }

    private static KeyValuePair<K, V> MakePair<K, V>(K k, V v) { return new KeyValuePair<K, V>(k, v); }

    private static void Main(string[] args)
    {
        var sw = Stopwatch.StartNew();
        var parser = new LRParser(
            MakePair("start", new string[] { "exps" }),
            MakePair("exps", new string[] { "exps", "exp" }),
            MakePair("exps", new string[] { }),
            MakePair("exp", new string[] { "INTEGER" })
        );
        Console.WriteLine(sw.ElapsedMilliseconds);
    }
}

这篇关于我在哪里可以找到一个_simple_，易于理解的实施LR（1）语法分析器发电机？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！