Создание кода разбора для нормального расширения форм Chomsky - PullRequest
Новая
       37

Создание кода разбора для нормального расширения форм Chomsky

0 голосов
/ 13 февраля 2020

Я хочу закодировать это, но я застрял

Итак, предположим, у нас есть грамматика 

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

Вот как будет выглядеть список после каждого l oop: 

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. Я l oop по LR и расширяю L до соответствующих значений RHS, которые будут (R. Это сделано. Тогда я хочу расширить R в LR, теперь я должен использовать L, а не (чтобы я мог достичь L). Хотя зацикливаясь, как я могу получить L, когда мой индекс перемещается в R?

Предположим, я расширяю S-> LR, RHS rhs - это список списков 

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 я должен снова вернуть L и расширить R, чтобы я получил L) .. поэтому мое окончательное расширение L будет (L и R)

Спасибо

1 Ответ

0 голосов
/ 13 февраля 2020

Когда вы пересекаете строку и расширяете каждый символ по его языковым правилам, вы создаете новую строку, расширяясь на месте. Вы не трансформируете исходную строку.

Например, если у вас есть LLTR и вы расширяете T, вы можете создать новую строку, используя подстроки, такие как [LL] + expand(T) + [R]

Один из способов сделать это - сохранить префикс, индексный символ и постфикс. Когда вы расширяете индекс, просто добавьте префикс и добавьте постфикс. Вы, вероятно, захотите создать новый список из списка rhs, а не преобразовывать сам rhs, в противном случае вам придется иметь дело с поддержанием индекса l oop в списке с изменяющимся размером.

Кажется, работает следующее: 

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");
        }

    }
}
...