Parser CSV używany we wtyczce jquery-csv
Jest to podstawowy parser gramatyki Chomsky'ego typu III .
Tokenizator wyrażeń regularnych służy do oceny danych według char-by-char. Po napotkaniu znaku sterującego kod jest przekazywany do instrukcji switch w celu dalszej oceny w oparciu o stan początkowy. Znaki niekontrolowane są grupowane i kopiowane masowo, aby zmniejszyć liczbę wymaganych operacji kopiowania ciągów.
Tokenizer:
var tokenizer = /("|,|\n|\r|[^",\r\n]+)/;
Pierwszy zestaw dopasowań to znaki sterujące: separator wartości („) separator wartości (,) i separator wprowadzania (wszystkie odmiany znaku nowej linii). Ostatnie dopasowanie obsługuje grupowanie znaków niekontrolowanych.
Analizator składni musi spełniać 10 reguł:
- Reguła # 1 - Jeden wpis na linię, każda linia kończy się nową linią
- Reguła # 2 - Końcowy znak nowej linii na końcu pliku został pominięty
- Reguła # 3 - Pierwszy wiersz zawiera dane nagłówka
- Reguła # 4 - Spacje są traktowane jako dane, a wpisy nie powinny zawierać przecinka końcowego
- Reguła # 5 - Linie mogą, ale nie muszą być ograniczone podwójnymi cudzysłowami
- Reguła # 6 - Pola zawierające podział wiersza, podwójne cudzysłowy i przecinki powinny być ujęte w cudzysłowy
- Reguła # 7 - Jeśli do zamykania pól stosuje się podwójne cudzysłowy, wówczas cytat pojawiający się w polu musi być poprzedzony innym podwójnym cudzysłowem
- Poprawka nr 1 - Pole nienotowane może lub może
- Poprawka nr 2 - Cytowane pole może, ale nie musi
- Poprawka nr 3 - Ostatnie pole we wpisie może zawierać wartość zerową lub nie
Uwaga: 7 najlepszych reguł pochodzi bezpośrednio z IETF RFC 4180 . Ostatnie 3 zostały dodane, aby objąć przypadki krawędzi wprowadzone przez nowoczesne aplikacje arkuszy kalkulacyjnych (np. Excel, Arkusz kalkulacyjny Google), które domyślnie nie ograniczają (tj. Cytują) wszystkich wartości. Próbowałem przyczynić się do zmian w RFC, ale jeszcze nie usłyszałem odpowiedzi na moje zapytanie.
Wystarczy z podsumowaniem, oto schemat:
Stany:
- stan początkowy dla wpisu i / lub wartości
- napotkano cytat otwierający
- napotkano drugi cytat
- napotkano niecytowaną wartość
Przejścia:
- za. sprawdza zarówno wartości cytowane (1), wartości niecytowane (3), wartości zerowe (0), wpisy zerowe (0) i nowe wpisy (0)
- b. sprawdza drugi znak zapytania (2)
- do. sprawdza, czy istnieje cytat (1), koniec wartości (0) i koniec wpisu (0)
- re. sprawdza koniec wartości (0) i koniec wpisu (0)
Uwaga: w rzeczywistości brakuje stanu. Powinien znajdować się wiersz od „c” -> „b” oznaczony stanem „1”, ponieważ drugi znak delimitera oznacza, że pierwszy separator jest nadal otwarty. W rzeczywistości prawdopodobnie lepiej byłoby przedstawić ją jako kolejne przejście. Ich tworzenie jest sztuką, nie ma jednego poprawnego sposobu.
Uwaga: Brakuje również stanu wyjścia, ale przy prawidłowych danych analizator zawsze kończy się na przejściu „a” i żaden ze stanów nie jest możliwy, ponieważ nie ma już nic do przeanalizowania.
Różnica między stanami a przejściami:
Stan jest skończony, co oznacza, że można go wywnioskować tylko z jednej rzeczy.
Przejście reprezentuje przepływ między stanami, więc może oznaczać wiele rzeczy.
Zasadniczo relacja stan-> przejście wynosi 1 -> * (tj. Jeden do wielu). Państwo definiuje „co to jest”, a przejście określa „jak sobie z tym poradzić”.
Uwaga: Nie martw się, jeśli zastosowanie stanów / przejść nie jest intuicyjne, nie jest intuicyjne. Zajęło mi trochę obszernej korespondencji z kimś znacznie mądrzejszym ode mnie, zanim w końcu udało mi się utrzymać koncepcję.
Pseudokod:
csv = // csv input string
// init all state & data
state = 0
value = ""
entry = []
output = []
endOfValue() {
entry.push(value)
value = ""
}
endOfEntry() {
endOfValue()
output.push(entry)
entry = []
}
tokenizer = /("|,|\n|\r|[^",\r\n]+)/gm
// using the match extension of string.replace. string.exec can also be used in a similar manner
csv.replace(tokenizer, function (match) {
switch(state) {
case 0:
if(opening delimiter)
state = 1
break
if(new-line)
endOfEntry()
state = 0
break
if(un-delimited data)
value += match
state = 3
break
case 1:
if(second delimiter encountered)
state = 2
break
if(non-control char data)
value += match
state = 1
break
case 2:
if(escaped delimiter)
state = 1
break
if(separator)
endOfValue()
state = 0
break
if(newline)
endOfEntry()
state = 0
break
case 3:
if(separator)
endOfValue()
state = 0
break
if(newline)
endOfEntry()
state = 0
break
}
}
Uwaga: To jest sedno, w praktyce jest o wiele więcej do rozważenia. Na przykład sprawdzanie błędów, wartości zerowe, końcowa pusta linia (tj. Która jest poprawna) itp.
W tym przypadku stan jest warunkiem rzeczy, gdy blok dopasowania wyrażenia regularnego kończy iterację. Przejście jest reprezentowane jako instrukcje przypadku.
Jako ludzie mamy tendencję do uproszczenia operacji niskiego poziomu do wyższego poziomu, ale streszczenia pracy z FSM jest praca z operacji niskim poziomie. Podczas gdy poszczególne stany i przejścia są bardzo łatwe do indywidualnej pracy, z natury trudno jest zobrazować całość naraz. Odkryłem, że najłatwiej jest podążać w kółko poszczególnymi ścieżkami wykonania, dopóki nie mogłem zrozumieć, jak przebiegają przejścia. Jest królem nauki matematyki, nie będziesz w stanie oceniać kodu z wyższego poziomu, dopóki szczegóły niskiego poziomu nie staną się automatyczne.
Poza tym: jeśli spojrzysz na faktyczną implementację, brakuje wielu szczegółów. Po pierwsze, wszystkie niemożliwe ścieżki spowodują określone wyjątki. Uderzenie ich nie powinno być możliwe, ale jeśli coś się zepsuje, absolutnie wyzwolą wyjątki w teście. Po drugie, reguły parsera dotyczące dozwolonego ciągu „legalnego” łańcucha danych CSV są dość luźne, więc kod potrzebny do obsługi wielu konkretnych przypadków krawędzi. Niezależnie od tego był to proces wyśmiewania FSM przed wszystkimi poprawkami błędów, rozszerzeniami i dostrajaniem.
Jak w przypadku większości projektów, nie jest to dokładna reprezentacja implementacji, ale przedstawia najważniejsze części. W praktyce z tego projektu pochodzą 3 różne funkcje analizatora składni: rozdzielacz linii specyficzny dla csv, analizator jednowierszowy i kompletny analizator składający się z wielu linii. Wszystkie działają w podobny sposób, różnią się sposobem obsługi znaków nowej linii.
