Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Java программирование > Общие вопросы по Java, Java SE, Kotlin
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 01.04.2017, 15:06   #1
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию Определение грамматики по Хомскому

Пытаюсь написать программы которая по введенными пользователем правилами будет определять тип грамматики.
Ввожу такие правила
S=AB
A=abA|E
B=cbB|E
убираю всю левую часть и знак "=", так же убираю знак "|" и "Е"
Написал правило для определения не выравненной регулярной грамматики:
Код:
    public static boolean regular( char[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (Character.isUpperCase(arr[0]) || Character.isUpperCase(arr[arr.length-1])) {
                return true;
            }
        }
        return false;
    }
Но при введенных выше правилах все равно возвращает false. Я так понял что это из-за того что убирая левую часть выражения и лишние символы я на их место ставлю нули и метод для регулярной грамматики видит на написанных мною местах именно нули.
Прошу помощи, и если есть идеи как это реализовать по другому, подскажите, а то я примеров не нашел, что сам придумал то и написал
Полный код:
Код:
import java.util.Scanner;
 
import javax.sound.midi.Soundbank;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Введите три правила");
        String p1 = in.nextLine(), p2 = in.nextLine(), p3 = in.nextLine();
        
        System.out.println("Правило 1:  " + p1);
        System.out.println("Правило 2:  " + p2);
        System.out.println("Правило 3:  " + p3);
        
        char[] arr1 = p1.toCharArray();
        char[] arr2 = p2.toCharArray();
        char[] arr3 = p3.toCharArray(); 
        
        rightSide(arr1);
        rightSide(arr2);
        rightSide(arr3);
        
        printArr(arr1);
        System.out.println();
        printArr(arr2);
        System.out.println();
        printArr(arr3);
        System.out.println(arr1.length);
        
        if (regular(arr1) && regular(arr2) && regular(arr3)) {
            System.out.println("Регулярная не выравненная граматика");
        }
        else {
            System.out.println("Fuck");
        }
    }
    
    
    public static char[] rightSide( char[] arr) {
        int i = 0;
        while (arr[i] != '=') {
            arr[i] = 0;
            i++;
        }
        
        for (i = 0; i < arr.length; i++) {
            if (arr[i] == '=' || arr[i] == ' ' || arr[i] == '|' || arr[i] == 'E') {
                arr[i] = 0;
            }
        }
        return arr;
    }
    
    public static void printArr( char[] arr) {
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
    }
    public static boolean regular( char[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (Character.isUpperCase(arr[0]) || Character.isUpperCase(arr[arr.length-1])) {
                return true;
            }
        }
        return false;
    }
}
Max00766 вне форума Ответить с цитированием
Старый 01.04.2017, 15:08   #2
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию

Думаю что возможно здесь нужно использовать динамичную структуру данных?
Max00766 вне форума Ответить с цитированием
Старый 01.04.2017, 17:47   #3
Pavia
Лис
Старожил
 
Аватар для Pavia
 
Регистрация: 18.09.2015
Сообщений: 2,409
По умолчанию

Какая-то бессмыслица, слово сочетании «выравненной грамматики» ни в одной из 20 книг по компилятором не встретилось.

Возьмите книгу Карпов Ю.Г. Основы построения трансляторов
И прочитайте про классификацию Хомского.

Цитата:
Написал правило для определения не выравненной регулярной грамматики:
определения куда? Так вы написали правило или Хомский?

Цитата:
public static boolean regular( char[] arr) {
for (int i = 0; i < arr.length; i++) {
if (Character.isUpperCase(arr[0]) || Character.isUpperCase(arr[arr.length-1])) {
return true;
}
}
return false;
}
Только всё наоборот, вам надо проверять на маленькие символы и на наличие «e». А вместо затирания левой части вам следует проверять на большие символы.
Хорошо поставленный вопрос это уже половина ответа. | Каков вопрос, таков ответ.
У дзен программиста программа делает то что он хотел, а не то что он написал .
Pavia вне форума Ответить с цитированием
Старый 01.04.2017, 17:58   #4
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию

Цитата:
Сообщение от Pavia Посмотреть сообщение
Какая-то бессмыслица, слово сочетании «выравненной грамматики» ни в одной из 20 книг по компилятором не встретилось.

Возьмите книгу Карпов Ю.Г. Основы построения трансляторов
И прочитайте про классификацию Хомского.

определения куда? Так вы написали правило или Хомский?


Только всё наоборот, вам надо проверять на маленькие символы и на наличие «e». А вместо затирания левой части вам следует проверять на большие символы.
Просто есть левая р-грамматика, есть правая, препод сказал что в моем случае она не выравненная
Max00766 вне форума Ответить с цитированием
Старый 05.04.2017, 14:01   #5
Max00766
Форумчанин
 
Регистрация: 15.11.2015
Сообщений: 151
По умолчанию

Написал программу, проблемы с контекстно-свободной и контекстно-зависимой грамматиками, прошу проверить код:
Код:
import java.util.Scanner;
 
public class Main {
 
    public static final String div = "=";
 
    public static void main(String[] args) {
        
        Scanner in = new Scanner(System.in);
        
        System.out.println("Введите три правила");
        String p1 = in.nextLine(), p2 = in.nextLine(), p3 = in.nextLine();
 
        System.out.println("Правило 1:  " + p1);
        System.out.println("Правило 2:  " + p2);
        System.out.println("Правило 3:  " + p3);
 
        String strArr1[] = p1.split(div);
        String strArr2[] = p2.split(div);
        String strArr3[] = p3.split(div);
 
        del(strArr1);
        del(strArr2);
        del(strArr3);
 
        if ((regularLeft(strArr1) && regularRight(strArr1)) || 
            (regularLeft(strArr2) && regularRight(strArr2))||
            (regularLeft(strArr3) && regularRight(strArr3)))  {
            System.out.println("Регулярная грамматика");
        } else if (regularLeft(strArr1) && 
                   regularLeft(strArr2) && 
                   regularLeft(strArr3)) {
            System.out.println("Регулярная левая грамматика");
        } else if (regularRight(strArr1) && 
                   regularRight(strArr2) && 
                   regularRight(strArr3)) {
            System.out.println("Регулярная правая грамматика");
        } else if (kS(strArr1) && 
                   kS(strArr2) && 
                   kS(strArr3)) {
            System.out.println("Контекстно свободна грамматика");
        } else if (kZ(strArr1) &&
                   kZ(strArr2) &&
                   kZ(strArr3)) {
            System.out.println("Контекстно зависимая грамматика");
        } else {
            System.out.println("Грамматика типа 0");
        }
 
    }
 
    public static void del(String[] arr) {
        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr[i].replace("|E", "");
        }
    }
 
    public static void printArr(String[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
    }
    // Регулярная грамматика
    public static boolean regular(String[] arr) {
        if (Character.isUpperCase(arr[1].charAt(0)) && 
            Character.isUpperCase(arr[1].charAt(arr[1].length() - 1))) {
            return true;
        }
        return false;
    }
    // Регулярная грамматика выравненная влево
    public static boolean regularLeft(String[] arr) {
        if (Character.isUpperCase(arr[1].charAt(0))) {
            return true;
        }
        return false;
    }
    // Регулярная грамматика выравненная вправо
    public static boolean regularRight(String[] arr) {
        if (Character.isUpperCase(arr[1].charAt(arr[1].length() - 1))) {
            return true;
        }
        return false;
    }
    // Контекстно свободна грамматика
    public static boolean kS(String[] arr) {
        String[] leftSide = arr[0].split("");
        String[] rightSide = arr[1].split("");
        for (int i = 0; i < leftSide.length; i++) {
            String s = leftSide[i];
            if (Character.isUpperCase(s.charAt(i)) && (leftSide.length == 1)) {
                return true;
            }
        }
        return false;
    }
    // Контекстно зависимая грамматика
    public static boolean kZ(String[] arr) {
        if (regular(arr) && regularLeft(arr) && regularRight(arr) && kS(arr)) {
            return true;
        }
        return false;
    }
}
Max00766 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Восстановление грамматики Faekus Фриланс 1 08.01.2017 23:16
построение эквивалентной грамматики acko Помощь студентам 0 25.12.2012 18:50
Грамматики, Синтаксические анализаторы, Парсеры Granus Обсуждение статей 5 27.06.2011 16:09
Преобразование регулярной грамматики в Конечный автомат. Vin0os Помощь студентам 0 03.04.2009 19:12
помогите! Дискретная математика, грамматики tywonka Помощь студентам 0 07.06.2008 13:46