AWK: Рекурсивный спуск CSV Parser

Question

В ответ на Recursive Descent CSV parser in BASH, I (the original author оба сообщений) сделал следующую попытку перевести его в AWK сценарий, для сравнения скорости обработки данных с этими языками сценариев. Перевод не является переводом 1: 1 из-за нескольких смягчающих факторов, но для тех, кто заинтересован, эта реализация быстрее при обработке строк, чем другая.

Первоначально у нас было несколько вопросов, которые были отменены благодаря Джонатану Леффлеру. Хотя название говорит CSV, мы обновили код до DSV, что означает, что вы можете указать любой отдельный символ в качестве разделителя полей, если вы сочтете это необходимым.

Этот код готов к вскрытию.

Основные характеристики

• Нет наложенные ограничения на длину ввода, длины поля, или количество поля
• Буквальное Цитируется Поля через двойные кавычки "
• ANSI C Управляющие последовательности как defined here в разделе 1.1.2 ^{[1] [2] [3]}
• Пользовательский разделитель ввода: The Art Of UNIX Programming (DSV) ^[4]
• Пользовательские Выход Сами разделяющие ^[5]
• UCS-2 и UCS-4 Escape-последовательности ^[6]

^[1] Цитируемые поля являются буквальным содержанием, поэтому интерпретации последовательности исключений не выполняются на цитированном контенте. Однако можно добиться конкатенации кавычек, простого текста и интерпретированных последовательностей в одном поле для достижения желаемого эффекта. Например:

one,two,three:\t"Little Endians," and one Big Endian Chief

Есть три поля линии CSV, где третье поле эквивалентно:

three:  Little Endians, and one Big Endian Chief

^[2] примеров, описанных в опорном материале как «реализация конкретной», или обладающие «неопределенным поведением», не будут поддерживаться, поскольку они не являются переносимыми по определению или слишком неоднозначными, чтобы быть надежными. Если escape-последовательность не определена здесь или в справочном материале, обратная косая черта будет проигнорирована, и один самый следующий символ будет рассматриваться как значение обычного текста. Целочисленные escape-последовательности символа значения не будут поддерживаться, это ненадежный метод, который не масштабируется хорошо на нескольких платформах и излишне, увеличивает сложность анализа по доверенности проверки.

^[3] Октальные символы escap должны быть в 3-значном восьмеричном формате. Если это не восьмеричная восьмеричная escape-последовательность, это однозначная escape-последовательность. Шестнадцатеричные escape-последовательности должны быть в двухзначном шестнадцатеричном формате. Если первые два символа, следующие за идентификатором escape-последовательности, недействительны, интерпретация не будет выполнена, и сообщение будет напечатано при стандартной ошибке. Любые оставшиеся шестнадцатеричные цифры игнорируются.

^[4] Пользовательский разделитель ввода iDelimiter должен быть одним символом. Многострочные записи не будут поддерживаться, и использование такого противоречия всегда должно быть неодобрительно. Это уменьшает переносимость записи данных, что делает ее специфичной для файла, местоположение и происхождение которого (внутри этого файла) могут быть неизвестны. Например, grep в файле для содержимого может возвращать неполную запись, потому что содержимое может начинаться с любой предыдущей строки, ограничивая сбор данных полным анализом базы данных сверху вниз.

^[5] Пользовательский разделитель oDelimiter может быть любым желательным строковым значением. Вывод скрипта всегда завершается одной новой строкой. Это функция правильного вывода терминала. В противном случае ваш разобранный вывод CSV и подсказка терминала будут использовать одну и ту же строку, создающую запутанную ситуацию. Кроме того, большинство интерпретаторов, таких как консоли, являются линейными устройствами, которые ожидают, что новая строка будет сигнализировать о завершении записи ввода-вывода. Если вы обнаружите, что конечная новая строка нежелательна, обрезайте ее.

^[6] 16-битные Юникода управляющие последовательности доступны через следующие обозначения:

 \uHHHH Unicode character with hex value HHHH (4 digits)

и 32-битные Unicode управляющие последовательности поддерживаются с помощью:

 \UHHHHHHHH Unicode character with hex value HHHHHHHH (8 digits)

---

Особая благодарность всем членам сообщества SO, чей опыт, время и вклад привели меня к созданию такого замечательно полезного инструмента для обработки информации.

Листинг: dsv.awk

#!/bin/awk -f 
# 
############################################################### 
# 
# ZERO LIABILITY OR WARRANTY LICENSE YOU MAY NOT OWN ANY 
# COPYRIGHT TO THIS SOFTWARE OR DATA FORMAT IMPOSED HEREIN 
# THE AUTHOR PLACES IT IN THE PUBLIC DOMAIN FOR ALL USES 
# PUBLIC AND PRIVATE THE AUTHOR ASKS THAT YOU DO NOT REMOVE 
# THE CREDIT OR LICENSE MATERIAL FROM THIS DOCUMENT. 
# 
############################################################### 
# 
# Special thanks to Jonathan Leffler, whose wisdom, and 
# knowledge defined the output logic of this script. 
# 
# Special thanks to GNU.org for the base conversion routines. 
# 
# Credits and recognition to the original Author: 
# Triston J. Taylor whose countless hours of experience, 
# research and rationalization have provided us with a 
# more portable standard for parsing DSV records. 
# 
############################################################### 
# 
# This script accepts and parses a single line of DSV input 
# from <STDIN>. 
# 
# Record fields are seperated by command line varibale 
# 'iDelimiter' the default value is comma. 
# 
# Ouput is seperated by command line variable 'oDelimiter' 
# the default value is line feed. 
# 
# To learn more about this tool visit StackOverflow.com: 
# 
# http://stackoverflow.com/questions/10578119/ 
# 
# You will find there a wealth of information on its 
# standards and development track. 
# 
############################################################### 

function NextSymbol() { 

    strIndex++; 
    symbol = substr(input, strIndex, 1); 

    return (strIndex < parseExtent); 

} 

function Accept(query) { 

    #print "query: " query " symbol: " symbol 
    if (symbol == query) { 
     #print "matched!"   
     return NextSymbol();   
    } 

    return 0; 

} 

function Expect(query) { 

    # special case: empty query && symbol... 
    if (query == nothing && symbol == nothing) return 1; 

    # case: else 
    if (Accept(query)) return 1; 

    msg = "dsv parse error: expected '" query "': found '" symbol "'"; 
    print msg > "/dev/stderr"; 

    return 0; 

} 

function PushData() { 

    field[fieldIndex++] = fieldData; 
    fieldData = nothing; 

} 

function Quote() { 

    while (symbol != quote && symbol != nothing) { 
     fieldData = fieldData symbol; 
     NextSymbol(); 
    } 

    Expect(quote); 

} 

function GetOctalChar() { 

    qOctalValue = substr(input, strIndex+1, 3); 

    # This isn't really correct but its the only way 
    # to express 0-255. On unicode systems it won't 
    # matter anyway so we don't restrict the value 
    # any further than length validation. 

    if (qOctalValue ~ /^[0-7]{3}$/) { 

     # convert octal to decimal so we can print the 
     # desired character in POSIX awks... 

     n = length(qOctalValue) 
     ret = 0 
     for (i = 1; i <= n; i++) { 
      c = substr(qOctalValue, i, 1) 
      if ((k = index("", c)) > 0) 
      k-- # adjust for 1-basing in awk 
      ret = ret * 8 + k 
     } 

     strIndex+=3; 
     return sprintf("%c", ret); 

     # and people ask why posix gets me all upset.. 
     # Special thanks to gnu.org for this contrib.. 

    } 

    return sprintf("\0"); # if it wasn't 3 digit octal just use zero 

} 

function GetHexChar(qHexValue) { 

    rHexValue = HexToDecimal(qHexValue); 
    rHexLength = length(qHexValue); 

    if (rHexLength) { 

     strIndex += rHexLength; 
     return sprintf("%c", rHexValue); 

    } 

    # accept no non-sense! 
    printf("dsv parse error: expected " rHexLength) > "/dev/stderr"; 
    printf("-digit hex value: found '" qHexValue "'\n") > "/dev/stderr"; 

} 

function HexToDecimal(hexValue) { 

    if (hexValue ~ /^[[:xdigit:]]+$/) { 

     # convert hex to decimal so we can print the 
     # desired character in POSIX awks... 

     n = length(hexValue) 
     ret = 0 
     for (i = 1; i <= n; i++) { 

      c = substr(hexValue, i, 1) 
      c = tolower(c) 

      if ((k = index("", c)) > 0) 
       k-- # adjust for 1-basing in awk 
      else if ((k = index("abcdef", c)) > 0) 
       k += 9 

      ret = ret * 16 + k 
     } 

     return ret; 

     # and people ask why posix gets me all upset.. 
     # Special thanks to gnu.org for this contrib.. 

    } 

    return nothing; 

} 

function BackSlash() { 

    # This could be optimized with some constants. 
    # but we generate the data here to assist in 
    # translation to other programming languages. 

    if (symbol == iDelimiter) { # separator precedes all sequences 
     fieldData = fieldData symbol; 
    } else if (symbol == "a") { # alert 
     fieldData = sprintf("%s\a", fieldData); 
    } else if (symbol == "b") { # backspace 
     fieldData = sprintf("%s\b", fieldData); 
    } else if (symbol == "f") { # form feed 
     fieldData = sprintf("%s\f", fieldData); 
    } else if (symbol == "n") { # line feed 
     fieldData = sprintf("%s\n", fieldData); 
    } else if (symbol == "r") { # carriage return 
     fieldData = sprintf("%s\r", fieldData); 
    } else if (symbol == "t") { # horizontal tab 
     fieldData = sprintf("%s\t", fieldData); 
    } else if (symbol == "v") { # vertical tab 
     fieldData = sprintf("%s\v", fieldData); 
    } else if (symbol == "0") { # null or 3-digit octal character 
     fieldData = fieldData GetOctalChar(); 
    } else if (symbol == "x") { # 2-digit hexadecimal character 
     fieldData = fieldData GetHexChar(substr(input, strIndex+1, 2)); 
    } else if (symbol == "u") { # 4-digit hexadecimal character 
     fieldData = fieldData GetHexChar(substr(input, strIndex+1, 4)); 
    } else if (symbol == "U") { # 8-digit hexadecimal character 
     fieldData = fieldData GetHexChar(substr(input, strIndex+1, 8)); 
    } else { # symbol didn't match the "interpreted escape scheme" 
     fieldData = fieldData symbol; # just concatenate the symbol 
    } 

    NextSymbol(); 

} 

function Line() { 

    if (Accept(quote)) { 
     Quote(); 
     Line(); 
    } 

    if (Accept(backslash)) { 
     BackSlash(); 
     Line();   
    } 

    if (Accept(iDelimiter)) { 
     PushData(); 
     Line(); 
    } 

    if (symbol != nothing) { 
     fieldData = fieldData symbol; 
     NextSymbol(); 
     Line(); 
    } else if (fieldData != nothing) PushData(); 

} 

BEGIN { 

    # State Variables 
    symbol = ""; fieldData = ""; strIndex = 0; fieldIndex = 0; 

    # Output Variables 
    field[itemIndex] = ""; 

    # Control Variables 
    parseExtent = 0; 

    # Formatting Variables (optionally set on invocation line) 
    if (iDelimiter != "") { 
     # the algorithm in place does not support multi-character delimiter 
     if (length(iDelimiter) > 1) { # we have a problem 
      msg = "dsv parse: init error: multi-character delimiter detected:"; 
      printf("%s '%s'", msg, iDelimiter); 
      exit 1; 
     } 
    } else { 
     iDelimiter = ","; 
    } 
    if (oDelimiter == "") oDelimiter = "\n"; 

    # Symbol Classes 
    nothing = ""; 
    quote = "\""; 
    backslash = "\\"; 

    getline input; 

    parseExtent = (length(input) + 2); 

    # parseExtent exceeds length because the loop would terminate 
    # before parsing was complete otherwise. 

    NextSymbol(); 
    Line(); 
    Expect(nothing); 

} 

END { 

    if (fieldIndex) { 

     fieldIndex--; 

     for (i = 0; i < fieldIndex; i++) 
     { 
      printf("%s", field[i] oDelimiter); 
     } 

     print field[i]; 

    } 

} 

---

Как запустить скрипт "как Pro"

# Spit out some CSV "newline" delimited: 
echo 'one,two,three,AWK,CSV!' | awk -f dsv.awk 

# Spit out some CSV "tab" delimited: 
echo 'one,two,three,AWK,CSV!' | awk -v oDelimiter=$'\t' -f dsv.awk 

# Spit out some CSV "ASCII Group Separator" delimited: 
echo 'one,two,three,AWK,CSV!' | awk -v oDelimiter=$'\29' -f dsv.awk 

Если вам нужны некоторые управления пользовательского вывода сепараторов, но не уверены, что использовать, вы можете обратиться к this handy ASCII chart

Будущие планы:

• библиотека C Реализация
консольного приложения
• C Реализация
• Представление в The Internet Engineering Task Force для возможной стандартизации

---

Philosp hy

Временные последовательности всегда должны использоваться для создания многострочных данных поля в базе данных на основе строк, а цитирование всегда должно использоваться для сохранения и конкатенации содержимого поля записи. Это самый простой (и, следовательно, самый эффективный) способ реализации парсера записи этого типа.Я рекомендую всем разработчикам программного обеспечения и образовательным учреждениям заняться этим делом и заявить об этом, чтобы обеспечить переносимость и точное получение разделенных разделителями записей на основе строк.

CSV не имеет официальных спецификаций, кроме RFC 4180, и не содержит никаких полезных переносных типов записей. Я надеюсь, что разработчик с опытом более 15 лет станет официально признанным стандартом для переносных CSV/DSV Records.

Answer 1

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

awk походит на C; он обрабатывает 0 как ложное и что-то ненулевое как истинное. Итак, что-либо большее, чем 0, верно, но все равно меньше 0.

Существует нет прямого способа печати на stderr в стандарте awk. GNU AWK документирует использование print "message" > "/dev/stderr" (имя как строка!) И подразумевает, что он может работать даже в системах без реального устройства. Он будет работать со стандартом awk также в системах с устройством /dev/stderr.

Идиома для обработки каждого индекса в массиве for (i in array) { ... }. Тем не менее, поскольку у вас есть индекс, itmIndex, сообщающее, сколько элементов в массиве, вы должны использовать

for (i = 0; i < itmIndex; i++) { printf("%s%s", item[i], delim); } 

и затем вывести символ новой строки в конце. Это приводит к тому, что один разделитель слишком много для моего мышления, но это транскрипция того, что делает код bash. Мой обычный трюк для этого:

pad = "" 
for (i = 0; i < itmIndex; i++) 
{ 
    printf("%s%s", pad, item[i]) 
    pad = delim 
} 
print ""; 

Вы можете передавать переменные в сценарий с -v var=value (или опустить -v). См. URL-адрес POSIX, указанный ранее.