bison/flex-Parser für Makefile-Grammatiken

Mupfel

Neues Mitglied
Grüß euch,

ich habe das "simple word count example" von https://github.com/jonathan-beard/simple_wc_example modifiziert, da ich Makefiles parsen möchte. Im Anhang findet ihm mein nicht-funktionierendes Ergebnis. Grammatiken sind nicht meine Stärke. Es würde mich freuen, wenn mal jemand mit Ahnung darüber schauen würde - oder mir sagen kann, ob bison/flex überhaupt für Makefile-Grammatiken geeignet sind.
Hintergrund ist, dass ich gerne mittels numactl Compiler-Prozessse an eine Node eines Zwei-Prozessor-Systems binden möchte. Das soll den Speicherbus zwischen den zwei Prozessoren entlasten. Mich interessiert, wie viel es schneller wird.

LG
Mupfel

EDIT: Ich hab mich im Forenbereich vertan, es gehört in den Bereich mit C/C++... Ist verschieben einfach oder soll ich dort neu erstellen? Mein Text darf editiert werden, wenn er verschoben wurde. EDIT2: Ja, hier passt es.
 

Anhänge

  • makefile-parser-test.zip
    13,5 KB · Aufrufe: 16
Zuletzt bearbeitet:
Die kleinen Anpassungen gegenüber dem Original kannst du auch ruhig als Codeblock posten. Dann kann auch jemand schnell einen Blick drauf werfen, ohne das Projekt runterladen und ausführen zu müssen.


Lexer:
C++:
#...

% %

#{
        std::cout
    << "###";
return token::COMMENT;
}

"\r\n" { return token::NEWLINE; }

"\n" {
  std::cout << "\n";
  return token::NEWLINE;
}

"\t" { return token::TAB; }

"=" { return token::ASSIGN; }

" " { return token::SPACE; }

^[^#][a - zA - Z0 - 9\._] + : {
  std::string s(yytext);
  std::cout << s;
  yylval->build<std::string>(s.substr(0, s.size() - 1));
  return token::RULE_NAME;
}

\"[^\a\b\f\n\r\t\v"]*\"    {
    std::string s(yytext);
std::cout << s.substr(1, s.size() - 2);
yylval->build<std::string>(s.substr(1, s.size() - 2));
return token::QUOTED_STRING;
}

[^\a\b\f\n\r\t\v "]+    {
    yylval->build<std::string>(yytext);
    std::cout << " " << yytext << " ";
    return token::STRING;
}
% %

#...

Parser:
C++:
#....

% token END 0 "end of file" % token<std::string> STRING % token<std::string> QUOTED_STRING % token<std::string> RULE_NAME % token NEWLINE % token TAB SPACE % token COMMENT %
    token ASSIGN

    % locations % start program

    % %

    program : block {
  std::cout << "x";
}
| comment { std::cout << "z"; }
| program block { std::cout << "y"; }
| program comment { std::cout << "a"; }
| END

        block : rule {
  std::cout << "b";
}
| assignment { std::cout << "c"; }

comment : COMMENT SPACE comment_eater NEWLINE { std::cout << "-"; }
| COMMENT NEWLINE { std::cout << "--"; }

comment_eater : STRING { std::cout << $1; }
| QUOTED_STRING { std::cout << $1; }
| comment_eater SPACE STRING { std::cout << $3; }
| comment_eater SPACE QUOTED_STRING { std::cout << $3; }

rule : RULE_NAME SPACE sources NEWLINE commands { std::cout << "target: " << $1; }

sources : sources STRING { std::cout << "source: " << $2; }
| sources QUOTED_STRING { std::cout << "source: " << $2; }
| STRING { std::cout << " source: " << $1; }
| QUOTED_STRING { std::cout << " source: " << $1; }
| % empty

            commands : commands NEWLINE STRING {
  std::cout << "command: " << $3;
}
| commands NEWLINE QUOTED_STRING { std::cout << "command: " << $3; }
| TAB STRING { std::cout << "command: " << $2; }
| TAB QUOTED_STRING { std::cout << "command: " << $2; }
| % empty

            assignment : STRING SPACE ASSIGN SPACE STRING NEWLINE {
  std::cout << "assignment: " << $1 << " " << $5;
}
| STRING SPACE ASSIGN SPACE QUOTED_STRING { std::cout << "assignment: " << $1 << " " << $5; }
| STRING SPACE ASSIGN { std::cout << "assignment: " << $1 << " cleared"; }

% %

#...

Kenne mich weder mit Lexern aus noch mit C++. Auf den ersten Blick fallen mir nur mehrere Sachen auf:
  1. das Tutorial ist ein bisschen umständlich aufgebaut, für einen einfachen Wordcounter.. nicht der beste Ausgangspunkt, weil du jetzt auch die Print-Ausgabe ändern musst, damit sie zum Tokencounter wird
  2. die Stringtoken-Definitionen im Lexer tun so, als würden sie Terminal-Eingaben in Echtzeit verarbeiten, und QUOTED_STRING sieht aus als wären die Ausführungszeichen falsch escaped... bleib doch erstmal bei ganz einfachen Strings, ohne all die Kontrollcharaktere
  3. benutz ein Minimal-Beispiel für eine Makefile und teste erstmal, ob die simpelsten Beispiele funktionieren
  4. nimm cmake für die Build-Konfiguration, dann siehst du mehr Details beim Bauen
Grad noch ausprobiert:

CMAKE:
mkdir build
cd build
cmake ..
make

> mc_lexer.l:71: bad character class
> mc_lexer.l:75: unrecognized rule
> mc_lexer.l:75: unrecognized rule

Ja, die Strings gefallen dem auch nicht.

oder mir sagen kann, ob bison/flex überhaupt für Makefile-Grammatiken geeignet sind.

Öh, wenn ich das richtig verstehe, sind Flex und Bison genau dafür gemacht und etwas Ähnliches wird sicher verwendet, um Makefiles zu verarbeiten oder zum Validieren/syntaktisch Hervorheben.

Habe nach einer offiziellen Definition gesucht, aber auf die schnelle nur Eigenbau-Beispiele gefunden. Hier ist eines, falls du ein bisschen "schummeln" willst:
 
Danke für die Ideen und die Codeblöcke!
EDIT: Sag mal, hast Du die Leerzeichen vor den Prozentzeichen selbst eingefügt oder war das was Anderes? Da sind auch einige Token in ein und die selbe Zeile gerutscht.

Meine Ergebnisse unterscheiden sich leider von Deinen:
make-Ausgabe:
[ 14%] [BISON][mc_parser] Building parser with bison 3.8.2
mc_parser.yy: Warnung: 2 Schiebe/Reduzier-Konflikte [-Wconflicts-sr]
mc_parser.yy: Bemerkung: mit Option „-Wcounterexamples“ laufen lassen, um Konflikt-Gegenbeispiele zu erzeugen
[ 28%] [FLEX][mc_lexer] Building scanner with flex 2.6.4
mc_lexer.l:84: warning, „-s“-Option gegeben, aber Vorgabe-Regel kann nicht passen
[ 42%] Building CXX object CMakeFiles/my_wc.dir/main.cpp.o
[ 57%] Building CXX object CMakeFiles/my_wc.dir/mc_driver.cpp.o
[ 71%] Building CXX object CMakeFiles/my_wc.dir/mc_lexer.yy.cc.o
[ 85%] Building CXX object CMakeFiles/my_wc.dir/mc_parser.tab.cc.o
[100%] Linking CXX executable my_wc
[100%] Built target my_wc
bison -Wcounterexamples:
../mc_parser.yy: Warnung: 2 Schiebe/Reduzier-Konflikte [-Wconflicts-sr]
../mc_parser.yy: Warnung: Schiebe/Reduzier-Konflikt bei Token STRING [-Wcounterexamples]
  Beispiel: • STRING
  Schiebe-Abweichung
    sources
    ↳ 17: • STRING
  Reduzier-Abweichung
    sources
    ↳ 15: sources   STRING
          ↳ 19: ε •
../mc_parser.yy: Warnung: Schiebe/Reduzier-Konflikt bei Token QUOTED_STRING [-Wcounterexamples]
  Beispiel: • QUOTED_STRING
  Schiebe-Abweichung
    sources
    ↳ 18: • QUOTED_STRING
  Reduzier-Abweichung
    sources
    ↳ 16: sources   QUOTED_STRING
          ↳ 19: ε •
"./my_wc Makefile"-Ausgabe:
ich@ryzen5:~/Downloads/makefile-parser-test/build> ./my_wc Makefile
### CMAKE CMAKE generated generated file: file: DO DO NOT NOT EDIT! EDIT!
-z### Generated Generated by byUnix MakefilesUnix Makefiles Generator, Generator, CMake CMake Version Version 3.30 3.30
-a
Error: syntax error at 1.100
Parse failed!!
Results:
Uppercase: 0
Lowercase: 0
Lines: 0
Words: 0
Characters: 0

Shell-Kram:
ich@ryzen5:~/Downloads/makefile-parser-test/build> flex --version
flex 2.6.4

ich@ryzen5:~/Downloads/makefile-parser-test/build> bison --version
bison (GNU Bison) 3.8.2
Geschrieben von Robert Corbett und Richard Stallman.

Copyright © 2021 Free Software Foundation, Inc.
Dies ist freie Software; die Kopierbedingungen stehen in den Quellen. Es
gibt keine Garantie; auch nicht für VERKAUFBARKEIT oder FÜR SPEZIELLE ZWECKE.

Ich bin jetzt erstmal verwirrt und habe ein rot blinkendes "GURU MEDITATION" vor dem inneren Auge.
 
Zuletzt bearbeitet:
Warum sind Teile deiner Ausgaben übersetzt? Schreibst du eigentlich auf Englisch?

Aber mal abgesehen davon:

Fehlermeldung​

Flex und Bison haben bei mir die gleiche Version. Als du mc_parser.yy direkt an bison übergeben hast, gibt er dir die Info, dass er nicht weiß, in welcher Reihenfolge er die Grammatik bei der source-Regel auflösen soll.

Also die hier:
C++:
sources : sources STRING { std::cout << "source: " << $2; }
| sources QUOTED_STRING { std::cout << "source: " << $2; }
| STRING { std::cout << " source: " << $1; }
| QUOTED_STRING { std::cout << " source: " << $1; }
| % empty

Eigentlich ist das ja alles rechts-terminiert, aber bin in Grammatiken grad nicht genug drin, um zu sehen, was ihm nicht gefällt.

Wäre eigentlich nützlich, wenn Bison dir einen Baum ausgeben könnte. Besonders, wenn man noch im Experimentier-Stadium ist. Vielleicht gibts das ja, aber ich habe nichts in der Art gesehen.

Testen​

Das manuelle Testen der Tokens ist ganz gut machbar und es berücksichtig auch die Regeln aus dem Parser. Eigentlich hat flex einen tollen Testmodus, in dem man interaktiv Token erkennen lassen kann. Im Tutorial wird das in ähnlicher Form durch my_wc -o umgesetzt. Hier fliegt man allerdings beim ersten Fehler raus. Trotzdem eine gute Möglichkeit zum Testen.

Damit man nicht zugespammt wird, muss man aber noch mc_driver.cpp anpassen oder in main.cpp den driver.print auskommentieren.

main.cpp:
int main(const int argc, const char **argv) {
  MC::MC_Driver driver;

  /** check for the right # of arguments **/
  if (argc != 2) {
    /** exit with failure condition **/
    return (EXIT_FAILURE);
  }

  if (std::strncmp(argv[1], "-h", 2) == 0) {
    /** simple help menu **/
    std::cout << "use -o for pipe to std::cin\n";
    std::cout << "just give a filename to count from a file\n";
    std::cout << "use -h to get this menu\n";
    return (EXIT_SUCCESS);
  }

  /** example for piping input from terminal, i.e., using cat **/
  if (std::strncmp(argv[1], "-o", 2) == 0) {
    driver.parse(std::cin);
  }
  /** example reading input from a file **/
  else {
    /** assume file, prod code, use stat to check **/
    driver.parse(argv[1]);
  }
  //driver.print(std::cout) << "\n";

  return (EXIT_SUCCESS);
}

Du kriegst zwar eine Bison-Warnung, aber es wird trotzdem kompiliert und man kann es interaktiv testen, zB mit CMake bauen und dann ausführen. Als möglicher Einzeiler, den man wiederholt im Basisverzeichnis ausführen kann:

mkdir build || true && popd||true && pushd build && cmake .. && make && popd && ./build/my_wc -o

Ergebnis:
Code:
build/my_wc -o
mkdir: cannot create directory ‘build’: File exists
-bash: popd: directory stack empty
/mnt/z/Projekte/Programmieren/DevCommunity/user/Mupfel/makefile-parser-test/build /mnt/z/Projekte/Programmieren/DevCommunity/user/Mupfel/makefile-parser-test
-- Configuring done
-- Generating done
-- Build files have been written to: /mnt/z/Projekte/Programmieren/DevCommunity/user/Mupfel/makefile-parser-test/build
Consolidate compiler generated dependencies of target my_wc
[100%] Built target my_wc
/mnt/z/Projekte/Programmieren/DevCommunity/user/Mupfel/makefile-parser-test
# dies ist ein kommentar
### dies dies ist ist ein ein kommentar kommentar
-z.PHONY: irgendeinblock
.PHONY: irgendeinblock  source: irgendeinblock
zuweisung = dings
 zuweisung target: .PHONYby dings
assignment: zuweisung dingscy
bla

Error: syntax error at 1.67
Parse failed!!

Könntest als Info erstmal die Tokennamen ausgeben lassen, anstatt direkt zu transformieren. Und Zeilen, die mit # beginnen kann man ja eigentlich komplett löschen/ignorieren, anstatt sie umzuwandeln. Ich glaube, dafür braucht man nicht mal eine Regel im Parser und auch keinen Comment-Eater.

Wie GNU Makefiles verarbeitet​


Die gnu-Seite war gestern offline bei mir, jetzt konnte ich endlich eine Info dazu finden, wie makefiles verarbeitet werden:

Hab jetzt den Quellcode nicht gefunden, aber liest sich erstmal so, als würde es nicht Grammatik-Konstrukte verwenden und eher situationsbedingt Strings abgleichen. Da kann man sich also eher schlecht die Grammatik abschauen.

CMake ist da vielleicht etwas nützlicher, auch wenn es Makefiles nur generiert und nicht liest, wenn ich das richtig verstehe. Aber immerhin hat es ein paar Lexer und Parser:

 
Ja, wenn ich dran denke, schreibe ich auf Englisch. Das verstehen mehr Leute als Deutsch.

Ich bin darauf gekommen, dass %empty es überflüssig machen dürfte, | STRING {...} und | QUOTED_STRING {...} in der sources-Grammatik zu haben. Das ergibt nämlich meines Erachtens die bemängelte Mehrdeutigkeit. Ich habe das mal herausgenommen und festgestellt, dass es immernoch nicht ganz will.

C++:
rule : RULE_NAME SPACE sources NEWLINE commands { std::cout << "target: " << $1; }
| RULE_NAME SPACE sources NEWLINE { std::cout << "target: " << $1; }

sources : sources STRING { std::cout << "source: " << $2; }
| sources QUOTED_STRING { std::cout << "source: " << $2; }
| % empty

            commands : commands NEWLINE STRING {
  std::cout << "command: " << $3;
}
| commands NEWLINE QUOTED_STRING { std::cout << "command: " << $3; }
| TAB STRING { std::cout << "command: " << $2; }
| TAB QUOTED_STRING { std::cout << "command: " << $2; }

Ich lasse .my_wc übrigens normalerweise auf das von CMake erzeugte Makefile los.
 
So sieht der Quoted String doch gleich besser aus:
C++:
\"(([^"])|(\\\"))*\"    {
    std::string s(yytext);
    std::cout << s.substr(1,s.size()-2);
    yylval->build< std::string >( s.substr(1,s.size()-2) );
    return token::QUOTED_STRING;
}

Newlines sollte der Parser auch berücksichtigen:
Code:
program : block { std::cout << "x"; }
| comment { std::cout << "z"; }
| program block { std::cout << "y"; }
| program comment { std::cout << "a"; }
| NEWLINE
| program NEWLINE
| END

Und es ist nicht zwangsläufig ein Leerzeichen nach der Raute:
C++:
comment : COMMENT SPACE comment_eater NEWLINE { std::cout << "-"; }
| COMMENT comment_eater NEWLINE { std::cout << "-"; }
| COMMENT NEWLINE { std::cout << "--"; }
EDIT: Kann eigentlich weg.

Rules sind auch nicht unbedingt mit Leerzeichen nach dem Doppelpunkt:
Code:
rule:
    RULE_NAME SPACE sources NEWLINE commands { std::cout << "target: " << $1; }
    | RULE_NAME SPACE sources NEWLINE { std::cout << "target: " << $1; }
    | RULE_NAME sources NEWLINE { std::cout << "target: " << $1; }

Der Lexer ist besser geeignet als Platz für das Kommentare-Rausfiltern, da er Leerzeichen sinnvoller berücksichtigt als der Parser:
Code:
#.*    {
    return token::COMMENT;
}
 
Zuletzt bearbeitet:
Das Ding frisst jetzt fehlerfrei Makefiles. Fehlt nur noch der Teil mit der Verteilung auf die Nodes. ;-)
Für Dual-Channel-Systeme wäre noch toll, zu wissen, welche Speicherbänke an welchen Prozessoren hängen. Hat das einer zur Hand? numactl --hardware sagt dazu nichts aus.

EDIT:
Der Lexer muss die RULE_NAME-Regel folgendermaßen haben:
Code:
^[^#\n][a-zA-Z0-9._%$()/]*[ \t]*:    {
    std::string s(yytext);
    yylval->build< std::string >( s.substr(0,s.size()-1) );
    return token::RULE_NAME;
}

Ansonsten sind schon bei CMake-generierten Dateien Zeilenvorschub-Zeichen (\n) am Anfang mancher RULE_NAMEs.
 

Anhänge

  • makefile-parser-test.zip
    13,5 KB · Aufrufe: 8
Zuletzt bearbeitet:
Zurück
Oben Unten