java - 为乔姆斯基范式扩展创建解析代码

Question

我想编写这个代码，但我卡住了

假设我们有一个语法

S→x|LR|LT
T→SR
L→(
R→)

以下是每次循环后列表的外观:

0 steps: [ S ]
1 step: [ x, LR, LT ]
2 steps: [ (R, L), (T, LSR ] 
3 steps: [ (), (), (SR, (SR, LxR, LLRR, LLTR, LS) ]

等等

假设我想检查字符串“(xx)”是否在语法中，所以我将进行 2n-1 次迭代，即 2x4-1=7 步。

我不知道如何编写代码来查看以下内容:

假设我在第2步。现在我想扩展LR。我循环 LR 并将 L 扩展为相应的 RHS 值，这将是 (R。这就完成了。然后我想在 LR 中扩展 R，现在我必须使用 L 而不是 (这样我就可以实现 L)。在循环时如何当我的索引移动到 R 时我得到 L？

假设我正在扩展 S->LR RHSrhs 是列表的列表

for(int j=0;j<rhs.size();j++){//size of list
      //size of every inside list such as {LR} 
      for(int k=0;k<rhs.get(j).length();k++){

            //compare every variable with L and if matches right hand side RHS of L
            //then move to R 


          }

我的问题

展开第 n 项时，如何将剩余的右侧项添加到当前展开式中，以及如何添加当前展开式的左侧项。

示例:我正在扩展 LR。如果 L 那么 (R 所以我必须用 ( 添加 R 。然后当我得到 (R i 必须再次取回 L 并展开 R 所以我得到 L) ..所以我对 L 的最终展开将是(L 和 R)

谢谢

Answer 1

当您遍历字符串并按其语言规则扩展每个字符时，您可以通过就地扩展来创建一个新字符串。您不转换原始字符串。

例如，如果您有 LLTR，并且要扩展 T，则可以使用 [LL] + Expand(T) + [R] 等子字符串创建一个新字符串

实现此目的的一种方法是维护前缀、索引字符和后缀。当您在索引处展开时，只需添加前缀并附加后缀即可。您可能希望从 rhs 列表中创建一个新列表，而不是转换 rhs 本身，否则您必须使用以下方法来维护列表上的循环索引不断变化的尺寸。

以下似乎有效:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;



class Main{

    public static List<String> expand(char c){
        switch(c){
            case 'S':
                return Arrays.asList(new String[]{"x", "LR", "LT"});
            case 'T':
                return Arrays.asList(new String[]{"SR"});
            case 'L':
                return Arrays.asList(new String[]{"("});
            case 'R':
                return Arrays.asList(new String[]{")"});
            default:
                throw new RuntimeException("Value not in language");
        }
    }

    public static Boolean isTerminal(char c){
        return c == 'x' || c == '(' || c == ')';
    }

    // For all expansions of c, prepend pre and append post
    public static List<String> expandInPlace(String pre, char c, String post){
        return expand(c).stream().map(str -> pre + str + post).collect(Collectors.toList());
    }

    public static void main(String[] args) {
        // Value entered on command line is string to check
        String checkString = args[0];
        int iterations = 2 * checkString.length() - 1;

        // Start with root of language "S"
        List<String> rhs = Arrays.asList(new String[]{"S"});
        for(int i=0; i<iterations; i++){
            // nextRhs is new list created by expanding the current list along language rules
            List<String> nextRhs = new ArrayList<>();
            for(int j=0; j<rhs.size();  
                String pre = "";
                String post = rhs.get(j);
                for(int k=0; k<rhs.get(j).length();k++){
                    // Treating pre and post like a double stack
                    // Popping the next character off the front of post
                    char expansionChar = post.charAt(0);
                    post = post.substring(1);
                    if(!isTerminal(expansionChar)){
                        nextRhs.addAll(expandInPlace(pre, expansionChar, post));
                    }
                    pre += expansionChar;
                }
            }
            rhs = nextRhs;
            System.out.println(rhs);
            System.out.println();
        }

        if(rhs.contains(checkString)){
            System.out.println(checkString + " is in the language");
        } else {
            System.out.println(checkString + " is not in the language");
        }

    }
}